BFS

문제: 맥주마시면서 걸어가기

현재 내 위치에서 편의점까지의 맨허튼 거리를 계산했을 때 1000이하이면 움직일 수 있지!
왜냐면 맥주 하나에 50미터 갈 수 있고 맥주가 20개 있으니까
그래서 편의점이 있는 곳마다 반복문을 돌면서 현재 내 위치에서 계산한 맨허튼 거리로 다음 편의점에 갈 수 있으면 큐에 넣어주고 이동~ 현재 내 위치가 페스티벌 장소와 같다면 'happy' 출력후 종료
갈 수 있을 만큼 갔는데 편의점 못가면 'sad' 출력~

from collections import deque
t = int(input())
def bfs(x, y):
	q = deque()
	q.append([x, y])
	visited = []
	while q:
		x, y = q.popleft()
        	# 현재 위치와 페스티벌 장소가 같으면 종료 
		if x == end_x and y == end_y:
			print('happy')
			return
            	# 갈 수 있는 편의점을 돌면서 현재 내 위치에서의 맨허튼 거리 계산, 그 편의점을 안갔다면 방문 처리후 이동
		for pos in conv:
			if abs(x - pos[0]) + abs(y - pos[1]) <= 1000 and pos not in visited:
				q.append([pos[0], pos[1]])
				visited.append([pos[0], pos[1]])
        # 끝까지 갔는데 못가면 'sad'
	print('sad')

# testcase 만큼 돌려
for i in range(t):
	n = int(input())
	start_x, start_y = map(int, input().split())
	conv = []
	for i in range(n):
		a, b = map(int, input().split())
		conv.append([a, b])
	end_x, end_y = map(int, input().split())
	conv.append([end_x, end_y])
    	# 시작점부터 BFS 실행
	bfs(start_x, start_y)