[BOJ/Python] 백준 9205번 - 맥주 마시면서 걸어가기

백준 #9205 맥주 마시면서 걸어가기

9205번: 맥주 마시면서 걸어가기

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

def can_go(now, dest):
  if abs(now[0] - dest[0]) + abs(now[1] - dest[1]) <= 1000:
    return True

def bfs(home, cvs_num, cvs, fesv, visited):
  q = deque()
  q.append(home)
  while q:
    now = q.popleft()
    if can_go(now, fesv):   # 도착지까지 갈 수 있는지
      return True
    for i in range(cvs_num):  # 편의점까지 갈 수 있는지
      if visited[i] and can_go(now, cvs[i]):
          q.append(cvs[i])
          visited[i] = False
  return False

t = int(input())   # 테스트 케이스 개수
for _ in range(t):
  cvs_num = int(input())   # 편의점 개수
  home = tuple(map(int, input().split()))  # 상근이네 집 좌표
  cvs = [tuple(map(int, input().split())) for _ in range(cvs_num)]   # 편의점 좌표
  fesv = tuple(map(int, input().split()))   # 페스티벌 좌표
  if bfs(home, cvs_num, cvs, fesv, [True for _ in range(cvs_num)]):
    print("happy")
  else:
    print("sad")

BFS로 푼 문제! 편의점 위치가 가까운 순으로 입력되는 줄 알고 단순하게 연산식으로 풀었다가 순서대로 들어오는 것이 아니라고 해서 너비우선탐색으로 다시 구현했다.

1. can_go 함수는 현재 위치에서 목적지까지 갈 수 있는지 계산한다.
2. bfs는 현재 위치에서 페스티벌까지 갈 수 있는지, 갈 수 없다면 편의점까지 갈 수 있는지 can_go 함수를 통해 반복 확인한다.
3. queue에서 좌표를 pop하여 현재 위치를 now에 저장한다.
4. 현재 위치(now)에서 페스티벌까지 갈 수 있다면 바로 True를 리턴한다.
5. 페스티벌까지 갈 수 없다면 갈 수 있는 편의점이 있는지 확인한다.
6. 갈 수 있는 편의점이 있다면 해당 편의점 좌표를 queue에 담는다. 그리고 해당 편의점을 queue에 담았음을 visited 리스트를 통해 표시한다.
7. 결국 queue에는 현재 위치에서 갈 수 있는 좌표가 담기게 된다.
8. 만약 queue가 빌 때까지 True를 리턴하지 못 했다면 페스티벌까지 갈 수 없음을 의미하여 False를 리턴한다.