[BOJ][python] 9205. 맥주 마시면서 걸어가기

 

https://www.acmicpc.net/problem/9205

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

---

💡IDEA

BFS를 사용하는 문제이다.

이 문제는 맥주를 50미터마다 하나씩, 20개씩 한 상자를 꾸준하게 마시고 편의점에서 채운다는 맥락에서 결국 1000미터 안에만 편의점이 있으면 된다는 것이 중요하다.

일반적인 BFS와 거의 유사하지만, 좌표 범위가 -32768 ≤ x, y ≤ 32767이므로 자주 사용하던 이차원 배열의 방문 확인용 배열을 만들기보다 그냥 방문한 좌표 자체를 저장하는 식으로 배열을 구성했다.

거리는 맨해튼 거리로 x좌표의 차이 + y좌표의 차이를 계산하여 1000미터 보다 작은 범위에 방문하지 않은 편의점만 있다면 충분하다.

맥주를 마시면서 페스티벌 좌표에 무사히 도착하면 "happy"를 출력하고 모든 큐를 다 소모하여 더이상 맥주를 마실 수 없게된다면 "sad"를 출력한다.🍺

 

📌CODE

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

def bfs(r, c):
    q = deque([(r, c)])
    v = [(r, c)]
    while q:
        cr, cc = q.popleft()
        if cr == er and cc == ec:
            return "happy"
        for pr, pc in path:
            d = abs(cr-pr) + abs(cc-pc)
            if d <= 1000 and (pr, pc) not in v:
                q.append((pr, pc))
                v.append((pr, pc))
    return "sad"

t = int(input())
for _ in range(t):
    path = []
    n = int(input())
    sr, sc = map(int, input().split())
    for _ in range(n):
        con_r, con_c = map(int, input().split())
        path.append((con_r, con_c))
    er, ec = map(int, input().split())
    path.append((er, ec))
    print(bfs(sr, sc))