[Python 파이썬] 백준 18126번 - 너구리 구구

2024년 8월 6일

문제 링크 : 백준 18126번 - 너구리 구구

 

문제

 

텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다.  구구의 집으로 들어가는 입구는 한 개이며 입구와 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.

구구는 스머프 동산에서 멜론아 아이스크림을 발견했다. 구구는 무더운 여름 햇살을 피해 최대한 입구에서 먼 방에 아이스크림을 숨기려고 한다.

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 5,000)이 주어진다.

다음 N-1개의 줄에 구구의 집의 모든 길의 정보가 정수 A, B, C(1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000)로 주어진다.

A번 방과 B번 방 사이를 양방향으로 연결하는 길의 길이가 C임을 의미한다.

출력

구구가 집 입구에서 멜론아 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구하여라.

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 너비 우선 탐색
• 깊이 우선 탐색

---

 

문제 접근

 

사이클이 존재할 수 있는 그래프 문제인지, 사이클이 존재하지 않는 트리 문제인지 적지 않은 시간 고민했다.

 

문제를 자세히 읽어보니 트리 문제라는 것을 알 수 있었는데 이는 문제의 다음 구문들 때문이었다.

 

1. 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다.

2. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다. 구구의 집으로 들어가는 입구는 한 개이며 입구와 모든 방들은 총 N-1개의 길로 서로 오고 갈 수 있다.

 

입구와 모든 방들은 서로 연결되어 있으며, 모든 N개의 방에 대해 N - 1 개의 길을 통해 모든 방을 서로 오갈 수 있다.

 

사이클이 존재하지 않는 트리의 정점이 V개일 때, 간선은 V - 1개이므로 이 문제는 사이클이 존재하지 않는 트리를 다루는 문제임을 알 수 있었다.

 

사이클이 존재했다면 다익스트라 알고리즘을 사용했겠지만, 이는 그렇지 않으므로 단순 BFS 로직으로 문제를 풀 수 있었다.

 

1번 정점으로부터 각 정점까지의 거리를 담아낼 distance 배열을 선언 후, 각 정점을 방문할 때마다 해당 정점까지 거리를 distance에 담아내 최종 BFS 로직이 끝나면 distance 배열의 최대값을 출력하도록 로직을 구성하였다.

---

입력 예제

 

4
1 2 3
2 3 2
2 4 4

 

 

 

출력 예제

 

7

 

 

---

전체 코드

 

# 18126
from collections import deque

def bfs():
    queue = deque()
    # 현재 탐색한 정점과 해당 정점까지의 거리
    queue.append([1, 0])
    visited[1] = True

    while queue:
        now_v, now_dis = queue.popleft()
        for next_v, next_dis in tree[now_v]:
            if not visited[next_v]:
                distance[next_v] = now_dis + next_dis
                visited[next_v] = True
                queue.append([next_v, distance[next_v]])

    return max(distance)



if __name__ == "__main__":
    N = int(input())
    tree = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        v1, v2, d = map(int, input().split())
        tree[v1].append([v2, d])
        tree[v2].append([v1, d])

    distance = [0 for _ in range(N + 1)]
    visited = [False] * (N + 1)

    print(bfs())

 

---

풀이 후기

 

문제 푸는 시간보다, 문제가 요구하는 바를 이해하는 데에서 시간을 더 사용했던 문제였다.