[BOJ][⚪2][백준#18126] 너구리 구구

문제 출처

BAEKJOON Online Judge #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임을 의미한다.

출력

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

예제

입력

4
1 2 3
2 3 2
2 4 4

출력

7

My Sol

import sys
from collections import deque

N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((w, v))
    G[v].append((w, u))

D = [1e14] * (N+1)

D[0] = D[1] = 0
Q = deque([1])
while Q:
    u = Q.popleft()
    for w, v in G[u]:
        if D[v] > D[u] + w:
            D[v] = D[u] + w
            Q.append(v)

maxx = 0
for n in range(2, N+1):
    if maxx < D[n] and D[n] != 1e14:
        maxx = D[n]

print(maxx)

다익스트라 알고리즘을 일부 활용해서 1번부터 v번까지의 가중치합 D[v]가 1번부터 u번까지의 가중치합 D[u]의 합과 u부터 v까지의 가중치 w를 더한 값보다 크다면, D[v]는 D[u]와 w를 더한 값으로 갱신된다. 그리고 이 지점에서 옮겨갈 수 있는 모든 지점에 대해 가중치합을 다시 계산하면서 갱신하면 되겠다.

마지막에는 D의 각 지점에서 제일 큰 값을 maxx에 지정하며, D의 기본값으로 지정한 1e14와 같다면 도착할 수 없는 방이므로 배제하면 된다.

결과

맞았습니다!!

가중치 C의 최댓값이 1e9인데, N이 최대 5,000이므로 극한의 상황에서 가중치 합이 5e12가 될 수 있다. 그런데 기본 값으로 1e11으로 두어 문제를 틀린 상황이 발생했다. 때문에 절대 될 수 없는 값으로 기본값을 지정할 필요가 있다.