[Python] Baekjoon - 9205. 맥주 마시면서 걸어가기

백준 9205번 맥주 마시면서 걸어가기는 그래프 탐색 알고리즘 중 BFS를 이용하여 해결할 수 있는 문제이다. 2차원 좌표평면 상에서 상근이가 맥주를 마시면서 축제장소까지 갈 수 있는 지를 구하는 문제다. 난이도는 실버 1이다.

 

맥주 마시면서 걸어가기 문제 정보

알고리즘 분류

- 그래프 탐색

- BFS

난이도

- 실버 1

맥주 마시면서 걸어가기 문제 요약

2차원 좌표평면 상에 상근이의 집, 축제장소, 그리고 N개의 편의점의 좌표가 주어진다. 상근이는 맥주 20병을 담을 수 있는 상자를 들고 출발하는데, 맥주 한 병을 마시면 50m를 갈 수 있다. 가다가 맥주가 모자라면 편의점에서 맥주를 구매하여 빈병을 맥주로 바꿀 수 있다. 상근이가 맥주를 마시면서 축제장소까지 갈 수 있는지의 여부를 구하여라.

 

문제 풀이 과정

• 처음에는 단순 그리디로 생각해서, 현재 지점에서 도착할 수 없으면 가장 가까운 편의점을 들리고, 그 위치에서 다시 같은 방식으로 반복하는 방법을 생각했다.
• 가장 가까운 편의점으로 가는 것이 틀리는 경우가 있어서 실패
• 한번에 최대 1000m(50m * 20)씩 갈 수 있다고 생각하고, BFS로 시작점부터 도착점까지 갈 수 있는지를 판단

코드

import sys
from collections import deque


def get_manhattan_dist(s, d):
    s_x, s_y = s
    d_x, d_y = d
    return abs(s_x-d_x) + abs(s_y-d_y)


def walk_with_drinking(T):
    global home, festival, cvs, visited

    queue = deque()
    queue.append(home)

    while len(queue) > 0:
        here = queue.popleft()
        dist = get_manhattan_dist(here, festival)

        # 현재 위치에서 축제까지 맥주 20개로 갈 수 있으면 True 반환하고 종료
        if dist <= 1000:
            return True

        # 축제까지 맥주 모자라는 경우 편의점 들리기
        for i in range(N):
            cvs_position = cvs[i]
            cvs_dist = get_manhattan_dist(here, cvs_position)
            if visited[i] != T and cvs_dist <= 1000:
                visited[i] = T
                queue.append(cvs_position)

    return False


if __name__ == '__main__':
    TC = int(input())
    cvs = []
    visited = [0 for _ in range(100)]
    home, festival = None, None

    for T in range(1, TC+1):
        N = int(input())
        home = tuple(map(int, sys.stdin.readline().split()))
        cvs.clear()
        for _ in range(N):
            cvs.append(tuple(map(int, sys.stdin.readline().split())))
        festival = tuple(map(int, sys.stdin.readline().split()))

        if walk_with_drinking(T):
            print("happy")
        else:
            print("sad")