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

1. 문제 설명

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

 

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

 

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

 

문제에서 짚어야 할 포인트는 다음과 같습니다:

📌 맥주는 최대 20병(= 1박스)까지 보유할 수 있다.

📌 50미터마다 한 병씩 마셔야 한다.

📌 편의점에 들러 맥주를 보충할 수 있다.

 

노드에서 목적지까지 이동할 때, 맥주를 한 병씩 마실 수 있어야 "행복하게" 이동이 가능하므로 1000미터(20병 X 50 미터)를 넘어서는 안 됩니다.

BFS로 이동 거리에서 편의점에 들러 맥주를 보충하며 이동할 때, 행복한 이동이 가능한지를 체크할 것입니다.

따라서, 시작 노드(상근이네 집)에서 페스티벌 좌표까지, 중간에 편의점 노드를 거치면서 이동한다면 행복한 이동(현재 노드에서 페스티벌 노드까지 1000미터가 안 됨)이 가능한지 확인하는 함수를 정의할 것입니다.

 

💡 노드 간의 거리가 1000미터를 넘지 않아야 한다.

💡 편의점 노드가 BFS의 다음 시작 노드가 되어야 한다.

 

9205번 바로가기>>

---

2. 입/출력 설명

1) 입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다.

각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

 

💡  노드 간의 거리 = abs(현재 x - 목표 x) + abs(현재 y - 목표 y)

 

2) 출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.

 

3) 예제

# Input
2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

# Output
happy
sad

---

3. 제출 코드

1) BFS 설명

BFS 함수는 시작 노드와 인접한 노드들을 먼저 탐색하는 방법으로, 멀리 떨어져 있는 노드를 가장 나중에 순회하는 방법입니다. 방문해야 할 노드가 담겨 있는 큐를 이용해 구현하고, 이전 문제에서는 노드를 방문할 때 +1/-1씩 이동했기 때문에 dx, dy를 사용하여 구현했습니다.

 

하지만 현재 문제에서는 더 이상 방문 가능한 편의점이 없고, 목적지(페스티벌 노드)까지 거리가 1000 이상이라면 "sad"를 출력할 수밖에 없습니다. 따라서, 큐에서 방문해야 할 노드는 시작 노드인 상근이의 집, 편의점 노드밖에 없습니다.

 

BFS 함수는 다음과 같이 구현 가능합니다.

def bfs():
    # node queue for BFS
    q = deque()
    q.append(start_node)

    while q:
        # current node x, y
        x, y = q.popleft()

        # 1) get distance between current node and dest node
        if abs(x - dest_node[0]) + abs(y - dest_node[1]) <= 1000:
            # distance <= 1000
            # friends will move happily
            print("happy")
            return

        # 2) distance > 1000
        # if there is a convenience stores
        for i in range(conv_num):
            if not visited[i]:  # if not visited
                # new node will be the conv node
                nx, ny = conv_node[i]

                # chech the distance between curr node and conv node
                if abs(x - nx) + abs(y - ny) <= 1000:
                    # distance <= 1000 (happily move)
                    # append node queue
                    # and check visited (conv node)
                    q.append([nx, ny])
                    visited[i] = 1

    # 3) after loop, we have to move sadly
    # there are no cases to move happily
    print("sad")
    return

 

1) 에서 현재 노드를 기점으로 페스티벌 노드까지의 거리가 1000 이하인 경우를 처리합니다.

거리가 1000 이하이기 때문에 친구들은 맥주 20병을 50미터마다 한 병씩 마시며 행복하게 이동할 수 있습니다.

이미 행복하게 이동할 수 있음이 증명됐으므로 함수를 종료합니다.

 

2) 에서 거리가 1000 미터보다 많이 남은 경우, 방문 가능한 편의점(conv node)이 있는지 확인합니다.

이때, 현재 노드에서 편의점까지의 노드 거리가 1000 미터 이하여야 하므로 확인해주고, 행복한 방문이 가능하다면 노드 큐에 새롭게 추가해줍니다.

 

3) 방문 가능 노드가 있는 동안 루프를 돌았음에도, 함수가 종료되지 않았다는 것은 행복한 방문이 불가능하다는 것을 의미합니다. 따라서 "sad"를 출력해줍니다.

 

2) 전체 코드

from collections import deque

def bfs():
    # node queue for BFS
    q = deque()
    q.append(start_node)

    while q:
        # current node x, y
        x, y = q.popleft()

        # get distance between current node and dest node
        if abs(x - dest_node[0]) + abs(y - dest_node[1]) <= 1000:
            # distance <= 1000
            # friends will move happily
            print("happy")
            return

        # distance > 1000
        # if there is a convenience stores
        for i in range(conv_num):
            if not visited[i]:  # if not visited
                # new node will be the conv node
                nx, ny = conv_node[i]

                # chech the distance between curr node and conv node
                if abs(x - nx) + abs(y - ny) <= 1000:
                    # distance <= 1000 (happily move)
                    # append node queue
                    # and check visited (conv node)
                    q.append([nx, ny])
                    visited[i] = 1

    # after loop, we have to move sadly
    # there are no cases to move happily
    print("sad")
    return


## Main ##
T = int(input())
for _ in range(T):
    # number of convenience stores
    conv_num = int(input())

    # get start node
    start_node = [int(x) for x in input().split()]

    # get nodes of convenience stores
    conv_node = []
    for _ in range(conv_num):
        x,y = map(int, input().split())
        conv_node.append([x, y])

    # get destination node
    dest_node = [int(x) for x in input().split()]

    # check visited node
    visited = [0 for i in range(conv_num + 1)]

    bfs()

---

4. 참고 코드 & 문제 출처

너무 오랜만에 알고리즘 문제를 다시 풀었더니, 감이 완전 다 떨어졌습니다..😭

leta 님의 코드를 참고해서 풀었어요.

https://letalearns.tistory.com/96

[Python] 백준 9205번 - 맥주 마시면서 걸어가기

 

코테 문제는 정말 꾸준히, 감을 잃지 않게 지속적으로 많이 푸는 게 중요한 것 같습니다.

앞으로도 다시 화이팅해보겠습니다!!

 

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