문제 출처

문제 유형

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

풀이

해당 문제는 solved.ac 사이트 기준 골드 4 문제입니다.

사이클이 없는 무방향 그래프인 트리가 주어지고, 어떤 두 노드를 선택해서 양쪽으로 좍 당긴 후 가장 길게 늘어나는 경우를 찾는 문제입니다.

• 트리의 노드는 1부터 n까지 번호가 매겨져 있다.

• 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다

• 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

저같은 경우에는 모든 정점에 대해 순회를 해야하는지를 깊게 고민했었는데, 보다 쉽게 dfs를 두 번 사용해서 값을 구할 수 있습니다. 특정 노드에서 가장 길이가 긴 노드를 선택하고, 그 노드에서 또 가장 길이가 긴 노드를 선택해 값을 구하는 방법입니다. 해당 방법의 증명식은 https://koosaga.com/14 에서 확인했습니다.

이 외에도 다익스트라(Dijkstra)로 해결하는 방법이 존재합니다.

풀이 코드

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

n = int(input())

tree = {}

def dfs(root, dist):
    for x in tree[root]:
        if distance[x[0]] == -1:
            distance[x[0]] = dist + x[1]
            dfs(x[0], dist + x[1])

for _ in range(n-1):
    # dict 생성
    s, e, d = map(int, input().split())

    if s not in tree:
        tree[s] = [(e,d)]
    else:
        tree[s].append((e,d))

    if e not in tree:
        tree[e] = [(s,d)]
    else:
        tree[e].append((s,d))

if n == 1:
    print(0)

else:
    # 첫번째 거리 구하기
    distance = [-1] * (n+1)
    distance[1] = 0
    dfs(1, 0)

    # 가장 긴 인덱스 설정
    maxIdx = distance.index(max(distance))

    # 두번째 거리 구하기
    distance = [-1] * (n+1)
    distance[maxIdx] = 0

    dfs(maxIdx, 0)

    print(max(distance))