[백준/파이썬] 1167번 트리의 지름

solved.ac Class 4레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

문제 해석

문제 풀이

먼저 주어진 입력을 잘 받도록 코드를 구현해야 한다.

 

임의의 두 점 사이의 거리 중 가장 긴 것을 구하기 위해서는 일반적으로 모든 노드를 dfs 탐색해야 한다.

하지만 이 경우 주어진 노드의 수가 10,000개 이므로 n^2의 시간복잡도에서 통과할 수 없다.

 

이러한 트리의 지름을 구하는 문제는 임의의 노드로 부터 가장 먼 노드를 구한 뒤,

가장 먼 노드로부터 가장 먼 거리를 구해주면 답을 구할 수 있다.

 

즉, 2번의 dfs를 통해 주어진 문제를 해결할 수 있으므로, n의 시간복잡도로 문제를 해결할 수 있다.

문제 코드

import sys
input = sys.stdin.readline

def solve(adj, v):
    visit = [0] * (v + 1)
    far_node = 0
    far_dist = 0
    def dfs(cur, dist):
        nonlocal visit
        nonlocal far_node
        nonlocal far_dist
        
        if dist > far_dist:
            far_node = cur
            far_dist = dist
        for next_node, next_dist in adj[cur]:
            if visit[next_node] == 0:
                visit[next_node] = 1
                dfs(next_node, next_dist + dist)
                visit[next_node] = 0
    # 아무 점으로 부터 dfs를 통해 가장 먼 노드 찾기
    visit[1] = 1
    dfs(1, 0)
    visit[1] = 0
    
    # 가장 먼 노드에서 가장 먼 노드까지의 거리 구하기
    far_dist = 0
    visit[far_node] = 1
    dfs(far_node, 0)
    return far_dist

v = int(input())
adj = [[] for _ in range(v + 1)]

for _ in range(v):
    temp = list(map(int, input().split()))
    cur = temp[0]
    for i in range((len(temp) - 2) // 2):
        idx = i * 2 + 1
        adj[cur].append((temp[idx], temp[idx + 1]))
print(solve(adj, v))

제출 결과

입력 부분을 잘 구현하자.
트리의 지름을 구하는 문제는 잊을만 하면 풀게 되는 것 같다..