⚠️ 문제
https://www.acmicpc.net/problem/1167
🔐 풀이
이 문제는 트리의 지름을 구하는 방법을 알고 있으면 쉽게 풀 수 있습니다.
트리의 지름을 구하는 방법은 아래와 같습니다.
- 트리의 임의의 노드(A)에서 가장 먼 노드(B)를 찾는다.
- 찾은 가장 먼 노드(B)에서 다시 가장 먼 노드(C)를 찾는다.
- 찾은 두 노드(B, C) 사이의 거리가 트리의 지름이 된다.
위 방법의 증명은 다른 블로그에서도 다룬 글이 많이 있으니 처음이라면 한 번 확인해보면 좋을 것 같습니다.
이 방법을 이용하기 위해 distance라는 다른 노드까지의 거리와 방문 여부를 확인하는 배열을 두고,
임의의 노드(1번 노드)에서 DFS를 통해 다른 노드까지의 거리를 구한 후 distance 배열에서 가장 큰 거리의 index를 찾으면 그곳이 가장 먼 노드의 번호가 됩니다.
찾은 노드에서 다시 가장 먼 노드를 DFS를 통해 다른 노드까지의 거리를 구하고 distance 배열에서 가장 큰 거리를 출력하면 그것이 트리의 지름입니다.
🧑🏻💻 코드
import sys
V = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(V + 1)]
for _ in range(V):
data = list(map(int, sys.stdin.readline().split()))
first_node = data[0]
for idx in range(1, len(data)-1, 2):
second_node, dist = data[idx], data[idx+1]
graph[first_node].append([dist, second_node])
def DFS(start, distance, graph):
for next_dist, next_node in graph[start]:
# 방문하지 않은 노드 탐색
if distance[next_node] == -1:
distance[next_node] = next_dist + distance[start]
DFS(next_node, distance, graph)
distance = [-1] * (V + 1)
distance[1] = 0
# 임의의 노드 1번에서 가장 먼 노드 찾기
DFS(1, distance, graph)
furthest_node = distance.index(max(distance))
distance = [-1] * (V + 1)
distance[furthest_node] = 0
# 찾은 가장 먼 노드에서 다시 가장 먼 노드 찾기
DFS(furthest_node, distance, graph)
print(max(distance))