[백준] 9205. 맥주 마시면서 걸어가기(python, 파이썬)

문제

9205. 맥주 마시면서 걸어가기

📌 아이디어

순서대로 편의점을 탐색하는 것이 아닌 가능한 모든 경우를 탐색해야되는 문제이기 때문에 BFS 탐색을 활용했습니다.

1. BFS 탐색을 통해 페스티벌을 도착할 수 있는 경로를 탐색
2. 집 좌표를 큐에 push
3. 주어진 모든 편의점 좌표를 탐색하며 가능한 경우에 큐에 push
4. 큐에서 pop된 좌표 중 페스티벌 좌표에 도달할 수 있으면 happy

📌 코드

from collections import deque
import sys

input = sys.stdin.readline

def bfs(i, j, x, y):
    que = deque()
    visited = [0] * N
    que.append([i, j])
    while que:
        ci, cj = que.popleft()
        # 페스티벌에 도착할 수 있는 경우
        if abs(x-ci) + abs(y-cj) <= 1000:
            return 'happy'
        for i in range(N):
            if visited[i] == 0:
                ni, nj = arr[i]
                # 이동가능 한 편의점인 경우
                if abs(ci-ni) + abs(cj-nj) <= 1000:
                    que.append([ni, nj])
                    visited[i] = 1
    # 페스티벌에 도착 못 하는 경우
    return 'sad'

T = int(input())
for _ in range(T):
    N = int(input())
    hx, hy = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    fx, fy = map(int, input().split())

    ans = bfs(hx, hy, fx, fy)
    print(ans)

피드백 및 개선점은 댓글을 통해 알려주세요😊