[python] 백준 - 9205 (맥주 마시면서 걸어가기)

2026.01.12ko 0 시리즈 · 알고리즘 #알고리즘

골드5 문제이며, 제한 시간은 1초이다.

문제

해결 과정

맥주를 들고 이동할 수 있는 최대 거리는 1000이다. 따라서 시작 지점부터 편의점이든 목적지든 맨해튼 거리가 1000 이하이면서, 아직 방문하지 않은 곳이라면 방문해서 큐에 넣어주는 방식으로 구현했다.

풀이

from collections import deque

def distance(a, b):
  x = abs(a[0] - b[0])
  y = abs(a[1] - b[1])
  return x + y

def bfs(x, y):
  queue = deque()
  queue.append((x, y))
  visited.add((x, y))

  while queue:
    x, y = queue.popleft()
    if x == dest[0] and y == dest[1]:
      return True
    for k in graph:
      if distance((x, y), k) <= 1000 and k not in visited:
        visited.add(k)
        queue.append(k)
  return False

t = int(input())
for _ in range(t):
  n = int(input())
  start = tuple(map(int, input().split()))
  graph = []
  for _ in range(n):
    graph.append(tuple(map(int, input().split())))
  dest = tuple(map(int, input().split()))
  graph.append(dest)
  visited = set()
  print('happy') if bfs(start[0], start[1]) else print('sad')

기존에 그래프 탐색을 쓰는 방식과는 다른 문제였다. 그렇게 많이 다르진 않았지만 어색한 느낌을 좀 받았다. 상하좌우가 아닌 각 노드로 바로 가는 1차원 그래프 탐색 느낌이었다. 또한 방문여부도 기존처럼 인덱스로 하지 않고, set 자료구조를 이용해 저장하는 것이 효과적이다.

아직 댓글이 없습니다.

문제

해결 과정

풀이

댓글

댓글 쓰기