[백준] 9205 - 맥주 마시면서 걸어가기 (Python)

🍻 요 문제는 bfs로 풀어야 깔끔하다! 처음에는 for문으로 풀다가 답이 이상해서 고냥 다시 bfs로 풀었다.

요 문제의 핵심은 queue에 담을 아이를 편의점 위치가 담겨 있는 다른 리스트에서 찾아야 하는 것!

import sys
input = sys.stdin.readline

def bfs(r, c):
    queue = [(r, c)]
    visited.append([r,c])
    while queue:
        x, y = queue.pop(0)
        ## 페스티벌 좌표에 다다르면 happy를 출력 
        if x == store[-1][0] and y == store[-1][1]:
            print('happy')
            return
        ## store에 담겨 있는 좌표 중에 현재의 거리와의 차이가 1000이하라면
        ## queue에 넣고, 방문 쳌을 한다. 
        for nx, ny in store:
            dist = abs(x-nx) + abs(y-ny)
            if dist <= 1000 and [nx, ny] not in visited:
                queue.append((nx, ny))
                visited.append([nx, ny])

    print('sad')

for tc in range(int(input())):
    ## 편의점 갯수
    n = int(input())
    house_x, house_y = map(int, input().split())
    store = []
    for _ in range(n+1):
        tmp = list(map(int, input().split()))
        store.append(tmp)

    visited = []
    bfs(house_x, house_y)