✅문제 요약

1. 맥주가 20병이 들어있는 박스를 들고 걸어가는데 50미터당 한 병씩 마신다.
2. 중간에 맥주를 파는 편의점을 들른다면 빈병을 새 병으로 교체할 수 있다.
3. 출발점, 편의점, 도착점 좌표가 주어지고 도착지에 도착할 수 있는지 출력

✅문제 풀이

일반적인 노드에서 갈 수 있는지 여부를 따지는 문제와 조금 다르게 느껴지지만 결국 BFS로 귀결되는 문제다.
1000m 즉 맥주 20병으로 편의점 또는 도착지에 갈 수 있는지를 너비우선 탐색을하여 진행했다

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

for tc in range(int(input())):
	# 편의점 개수
    n = int(input())
    # 집 위치
    home = list(map(int, input().split()))
    # 편의점 위치들
    graph = [list(map(int, input().split())) for _ in range(n)]
    # 도착지
    fest = list(map(int, input().split()))
	
    # 방문처리
    visit = [0]*(n+1)

	# 현재위치 큐
    Q = deque([(home[0], home[1])])
    while Q:
        x, y = Q.popleft()
		
        # 현재 위치에서 1000m(맥주 20병*50m) 이내에 도착지가 있다면 종료
        if abs(x-fest[0]) + abs(y-fest[1]) <=1000:
            print('happy')
            break
		
        # 편의점 위치를 돌며 1000m 이내에 있다면 그 위치로 이동
        for i in range(n):
            if not visit[i]:
                r, c = graph[i]
                if abs(x-r)+abs(y-c)<=1000:
                    Q.append((r, c))
                    visit[i] = 1
    else:
        print('sad')