[Python] 백준 <9205-맥주 마시면서 걸어가기>

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

 

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

def bfs(house_x, house_y):
    dq = deque()
    dq.append((house_x, house_y))

    while dq:
        x, y = dq.popleft()
        # 20병으로 페스티벌에 갈수 있으면 bfs 종료
        if abs(x-festival[0]) + abs(y-festival[1]) <= 1000:
            print("happy")
            return
        for i in range(N): 
            # 해당 편의점을 방문하지 않았으면
            if not visited[i]: 
                mart_x, mart_y = mart[i] 
                # 해당 편의점까지 갈 수 있으면
                if abs(x-mart_x) + abs(y-mart_y) <= 1000:
                    visited[i] = 1 
                    # 편의점 좌표 저장
                    dq.append((mart_x, mart_y)) 
    print("sad")
    return

T = int(input())

for _ in range(T):
    N = int(input())
    house = list(map(int, input().split(" ")))
    mart = list()
    for _ in range(N):
        mart.append(list(map(int, input().split(" "))))
    festival = list(map(int, input().split(" ")))

    visited = [0]*(N)
    bfs(house[0], house[1])