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

💁🏻  문제

9205번: 맥주 마시면서 걸어가기

---

🤷🏼‍♀️  문제 설명

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 출발은 상근이네 집에서 하고, 20병이 들어있는 맥주 한 박스를 들고 출발한다. 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다.
따라서 가는동안 맥주가 떨어진다면 맥주를 더 구매하기 위해 편의점에 들릴 수 있다. 맥주를 파는 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있지만 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 페스티벌에 도착할 수 있는지 여부를 구하시오.
각 좌표 사이의 거리는 x좌표의 차이 + y좌표의 차이(맨해튼 거리)이다.

 

⚙️  풀이

방문할 수 있는 좌표를 갱신하며 순차적으로 탐색을 수행하면 된다.
좌표를 순차적으로 탐색하기 위해 queue를 사용한 BFS로 풀어낼 수 있다.

처음에는 queue를 사용하지 않고 그냥 현재 위치(x, y)를 갱신하는 방법으로만 구현하려 했다.
하지만 이 풀이법은 방문할 수 있는 모든 좌표에 대한 탐색을 수행할 수 없으므로 불가능하다.
순차적으로, 모든 경우의 수에 대해 최소 비용의 탐색을 수행하려는 경우 그냥 queue를 사용하자.

import sys
from collections import deque


t = int(input())
for tc in range(t):
    n = int(input())
    sx, sy = map(int, sys.stdin.readline().split())
    store = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    visited = [0 for i in range(n + 1)]
    dx, dy = map(int, sys.stdin.readline().split())

    answer = 'sad'
    queue = deque()
    queue.append((sx, sy))
    # 맥주가 충분하거나, 갈 수 있는 편의점이 남아있어 맥주를 살 수 있는 경우를 모두 탐색
    while queue:
        x, y = queue.popleft()

        # 페스티벌에 갈 수 있는 경우(= 필요한 맥주가 박스에 들어있는 맥주보다 적은 경우)
        need = abs(dx - x) + abs(dy - y)
        if need <= 1000:
            answer = 'happy'
            break

        # 맥주가 바닥나게 되는 경우, 편의점 탐색
        for i, (store_x, store_y) in enumerate(store):
            if visited[i]:
                continue
            store_need = abs(x - store_x) + abs(y - store_y)
            if store_need <= 1000:
                visited[i] = True
                queue.append((store_x, store_y))
    print(answer)