[백준] 9205번 맥주 마시면서 걸어가기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/9205
• BFS (너비 우선 탐색)

 

from collections import deque

t = int(input())

def bfs():
    n = int(input()) # 편의점 개수
    homeX, homeY = map(int, input().split())  # 상근이 집

    li = [] # 좌표 리스트
    ck = [0] * (n+1) # 체크 리스트

    for i in range(n):  # 편의점 좌표 입력 받고 리스트에 추가
        li.append(list(map(int, input().split())))
        
    endX, endY = map(int, input().split())  # 페스티벌장 좌표
    li.append([endX, endY]) # 페스티벌장 좌표도 리스트에 추가

    q = deque([[homeX, homeY]])   # 상근이 집부터 시작

    while q:
        x, y = q.popleft()

        if x == endX and y == endY: # 도착하면
            return print("happy")

        for i in range(len(li)):
            if abs(x - li[i][0]) + abs(y - li[i][1]) <= 1000 and ck[i] == 0:
                ck[i] = 1
                q.append(li[i])
        
    return print("sad")


for i in range(t):
    bfs()