[백준]9205번: 맥주 마시면서 걸어가기

https://www.acmicpc.net/problem/9205

 

---

• 50m당 맥주 1병이 소진된다는 말은, 한 번에 최대 1000m까지 이동할 수 있다는 뜻이다.
• 이동 경로:

 집 (-> 편의점1 -> 편의점2 -> .... -> 편의점n) -> 페스티벌

 

• 각각의 이동 거리가 1000보다 크지 않은 상태를 유지하며 도착지까지 도달하게 되면 happy를 출력하면 되는 문제이다.

 

import sys
from collections import deque
input = sys.stdin.readline

def dist(x1, y1, x2, y2):
  return abs(x1-x2) + abs(y1-y2)

def bfs(x,y):
  q = deque()
  q.append((x,y))
  visited=[] #방문한 편의점 좌표를 저장
  while q:
    a,b=q.popleft()
    #이동거리 1000이하로도착점에 도달하면 True를 출력
    if dist(a,b,endX,endY) <= 1000: 
      return True
    #편의점들 중 들를 수 있는 곳이 있는지 체크
    for i in range(n):
      storeX, storeY = store[i]
      #방문한 적 없고 거리 1000이하로 갈 수 있는 편의점을 찾으면 방문처리후 큐에 넣는다
      if (storeX, storeY) not in visited:
        if dist(a,b,storeX,storeY) <= 1000:
          visited.append((storeX, storeY))
          q.append((storeX,storeY))
  return False

  
t=int(input())

for _ in range(t):
  n = int(input())
  startX, startY = map(int, input().split())
  store=[]
  for i in range(n):
    x,y = map(int,input().split())
    store.append((x,y))
  endX, endY = map(int, input().split())

  if bfs(startX, startY)==True:
    print('happy')
  else:
    print('sad')

어려웡