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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 9205번 맥주 마시면서 걸어가기
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

집에서 페스티벌까지 편의점을 경유해 맥주 20병(1000m) 제약 안에서 이동 가능한지 판별하는 문제입니다.

코드

import collections
import sys;read=sys.stdin.readline

def getDistance(a,b): return abs(a[0]-b[0])+abs(a[1]-b[1])

for T in range(int(read())):
    n=int(read())
    h=tuple(map(int,read().split()))
    cs=[tuple(map(int,read().split())) for _ in range(n)]
    p=tuple(map(int,read().split()))
    cs.append(p)

    q=collections.deque([h])
    f=False
    while q:
        cur=q.popleft()
        if cur==p:
            f=True
            break
        for c in cs:
            d = getDistance(cur,c)
            if d <= 1000:
                q.append(c)
                cs.remove(c)
        
    print('happy' if f else 'sad')

설명

현재 위치에서 맨해튼 거리 1000 이하로 갈 수 있는 지점을 BFS로 확장해 페스티벌 도달 여부를 happy/sad로 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---