백준 9205 맥주 마시면서 걸어가기 (파이썬)

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

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

1. 편의점과 도착지 좌표를 d에 저장

2. d안의 좌표를 하나씩 불러오면서 현재 위치와의 맨해튼 거리와 맥주양을 비교하여 이동가능한지 검사

3. bfs로 이동하면서 목표에 도착하면 happy 출력 불가능하면 sad 출력 

from collections import deque
import sys

input = sys.stdin.readline

def bfs(x, y):
    q, c = deque(), []
    q.append([x, y, 20])
    c.append([x, y, 20])
    while q:
        x, y, beer = q.popleft()
        if x == x1 and y == y1:
            print("happy")
            return
        for nx, ny in d:
            if [nx, ny, 20] not in c:
                l1 = abs(nx - x) + abs(ny - y)
                if beer*50 >= l1:
                    q.append([nx, ny, 20])
                    c.append([nx, ny, 20])
    print("sad")
    return

tc = int(input())
while tc:
    n = int(input())
    x0, y0 = map(int, input().split())
    d = []
    for _ in range(n):
        x, y = map(int, input().split())
        d.append([x, y])
    x1, y1 = map(int, input().split())
    d.append([x1, y1])
    bfs(x0, y0)
    tc -= 1