문제
간선에 가중치가 있는 트리가 주어질 때, 트리의 지름(가장 멀리 떨어진 두 노드 사이의 거리)을 구하는 문제다. 모든 노드 쌍을 확인하면 O(N^2)이지만, "임의의 노드에서 가장 멀리 있는 노드가 지름의 한쪽 끝점"이라는 트리의 성질을 이용하면 DFS 2번으로 O(N)에 해결된다.
입력
- 첫째 줄: 노드 수 N (1 이상 10,000 이하)
- 둘째 줄부터 N-1개 줄: 부모 u, 자식 v, 간선 가중치 w
출력
트리의 지름(두 노드 간 최대 거리)을 출력한다.
예제
| 입력 | 출력 |
|---|---|
12 1 2 3 1 3 2 2 4 5 3 5 11 3 6 9 4 7 1 4 8 7 5 9 15 5 10 4 6 11 6 6 12 10 | 45 |
풀이
DFS 두 번으로 트리의 지름을 찾는 2-DFS 알고리즘을 적용한다.
- 루트(노드 0)에서 DFS를 실행하여 가장 멀리 있는 노드
midx를 찾음 midx는 지름의 한쪽 끝점임이 보장됨midx에서 다시 DFS를 실행하여 가장 먼 거리를 구함 — 이 값이 트리의 지름- DFS 내부에서 현재 누적 거리가 최댓값보다 크면
ans와midx를 갱신
핵심 아이디어: 트리에서 임의의 한 노드로부터 가장 먼 노드 u를 구하고, u에서 다시 가장 먼 노드까지의 거리를 구하면 그것이 트리의 지름이 된다는 수학적 증명을 이용한다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Day132BOJ1967트리의지름DFS { // 1967 트리의 지름
static int N, ans, midx;
static List<int[]>[] nodes;
static boolean[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
ans = 0;
midx = 0;
nodes = new ArrayList[N];
for (int i = 0; i < N; i++)
nodes[i] = new ArrayList<>();
for (int i = 1; i < N; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken()) - 1;
int c = Integer.parseInt(st.nextToken());
nodes[u].add(new int[] { v, c });
nodes[v].add(new int[] { u, c });
}
// 부모노드부터 가장 멀리 있는 노드
visited = new boolean[N];
visited[0] = true;
dfs(0, 0);
// 가장 멀리 있는 노드에서 가장 멀리 있는 노드
visited = new boolean[N];
visited[midx] = true;
dfs(midx, 0);
System.out.println(ans);
br.close();
}
private static void dfs(int idx, int sum) {
if (ans < sum) {
ans = sum;
midx = idx;
}
for (int[] a : nodes[idx]) {
int ed = a[0];
int cost = a[1];
if (!visited[ed]) {
visited[ed] = true;
dfs(ed, sum + cost);
}
}
}
}복잡도
- 시간: O(V + E)
- 공간: O(V + E)