[파이썬] 백준 알고리즘 No.9205 맥주 마시면서 걸어가기

나의 코드

import sys
from collections import deque
input = sys.stdin.readline
t = int(input())

def bfs():
    queue = deque()
    queue.append((home_x, home_y))

    while queue:
        x, y = queue.popleft()
        if abs(x - dest_x) + abs(y - dest_y) <= 1000:
            print("happy")
            return
        for i in range(n):
            if not visited[i]:
                a, b = graph[i]
                if abs(x - a) + abs(y - b) <= 1000:
                    visited[i] = True
                    queue.append((a, b))
    print("sad")
    return


for _ in range(t):
    n = int(input())
    home_x, home_y = map(int, input().split())

    graph = []
    for _ in range(n):
        x, y = map(int, input().split())
        graph.append((x, y))
    dest_x, dest_y = map(int, input().split())
    visited = [False for _ in range(n + 1)]
    bfs()

 

풀이 방법

처음에는 정렬 후 그리디나 구현으로 풀 수 있을거라 생각했지만

1. 좌표가 주어지는 순서대로 이동한다는 보장이 없음

2. 좌표가 음수 값을 지닐 수도 있음

해당 문제로 인해 각 지점을 그래프의 노드로 생각하여 전체탐색 후 성공.