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

문제 설명

 

입출력 예제

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

---

풀이 코드

이 문제의 핵심 내용만 정리하면 다음과 같다.

• 현재 20병의 맥주를 가지고 있다. 50미터에 한 번씩 맥주 한 병을 마신다. (즉, 한번에 1000m를 갈 수 있다.)
• 편의점에 갈 때마다 새로운 맥주를 20병 얻을 수 있고 나선 직후 50미터에 한 번씩 맥주 한 병을 마신다. (즉, 편의점 위치 부터 페스티벌 까지 이동을 시작한다.)
• 시작위치에서 페스티벌까지 (1000m = 맥주 20개 * 50m) 갈수 있다면 "happy" 없다면 "Sad"를 반환한다.

 

정답 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
    q = deque()
    q.append((home_x, home_y))

    while q:
        x, y = q.popleft()
        # 맥주 20개로 페스티발에 도착할 수 있을 경우 happy 반환 후 종료
        if abs(x - festival_x) + abs(y - festival_y) <= 1000: # (맨해튼 거리)
            print("happy")
            return
        # 한번에 도착할 수 없을 경우, 편의점 방문
        for i in range(n): 
            if not visited[i]:
                new_x, new_y = market[i]
                if abs(x - new_x) + abs(y - new_y) <= 1000: # (맨해튼 거리)
                    q.append((new_x, new_y)) # 편의점의 위치부터 다시 시작
                    visited[i] = 1
    print("sad") # 페스티벌에 도착하지 못할 경우

t = int(input())
for i in range(t):
    n = int(input())
    home_x,home_y = map(int, input().split())
    market = []
    for _ in range(n):
        maeket_x, market_y = map(int, input().split())
        market.append((maeket_x, market_y))
    festival_x, festival_y = map(int, input().split())
    visited = [False] * (n + 1)
    bfs()