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

from collections import deque
t = int(input())
for _ in range(t):
    n = int(input())
    p = []
    sx, sy = map(int, input().split())
    for _ in range(n):
        px, py = map(int, input().split())
        p.append((px, py))
    rx, ry = map(int, input().split())
    p.append((rx, ry))

    check = [-1] * len(p)
    q = deque()
    q.append((sx, sy))
    while q:
        x, y = q.popleft()
        for i in range(len(p)):
            tx, ty = p[i]
            if abs(x-tx)+abs(y-ty) <= 1000 and check[i] == -1:
                check[i] = 0
                q.append((tx, ty))
    if check[-1] == 0:
        print("happy")
    else:
        print("sad")

점과 점 사이가 20(맥주) * 50(맥주 한병으로 갈 수 있는 거리) = 1000미터를 넘지 않는다고 알고 bfs로 완탐