[BOJ/C++] 1167번 트리의 지름
문제
문제 해석
트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 찾아야 한다. 언뜻 보면 모든 노드에 대해서 가장 먼 노드를 찾고, 길이를 비교해야 할 것 같지만, 노드의 개수가 10^5 라는 점에서 고민이 필요했다.
문제에 주어진 예시를 그림으로 표현하면 위와 같다. 우선 모든 노드에서 가장 먼 노드를 찾아보았다. 5번 노드가 자기 자신을 제외한 모든 노드들에서 멀다고 판단 되었다.
5번 노드의 특징을 살펴보았다. 그림에서 알 수 있듯이, ✅ 5번 노드는 자기 자신을 제외한 어떤 노드를 root 노드로 정하더라도 항상 leaf 노드이다.
그러므로, 임의의 노드를 하나 정하고, 그 노드에서 가장 먼 노드인 트리의 leaf 노드를 찾는다.
여기까지 판단하고 나서, leaf 노드에서 가장 먼 노드까지의 길이가 트리의 지름이 될 것이라고 짐작은 했지만, 확신을 하지 못해서 구현을 망설였다. 이 문제의 풀이를 올려둔 많은 블로그들을 확인한 결과, 이 블로그의 설명이 크게 와닿았다. 확실하게 증명된 것을 확인하고 싶다면 참고하길 바란다.
놓친 부분
✅ 노드의 개수가 10^5 처럼 클 때에는 2차원 배열로 가중치를 입력 받는 것이 큰 낭비이다. 정확히 간선의 개수만큼만 메모리를 차지하도록 선언하고 구현하는 연습을 하자.
구현 방향
변수 선언
✅ memset(visited, 0, sizeof(visited));와 같이 initialize를 하기 위해 memset을 사용하는 경우 #include <string.h>를 확인하자.
✅ 간선의 개수만큼만 메모리를 차지하도록 선언한다. vector<pair<int, int>> graph[100001];
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int V;
vector<pair<int, int>> graph[100001];
int visited[100001];
int max_weight = 0;
int farthest_node = 0;
int main()
// input
✅다른 문제들과 다르게 입력 받는 것이 독특하다.
DFS 알고리즘으로 leaf 노드를 찾고, leaf 노드에서 가장 먼 노드를 찾아서 트리의 지름을 찾는다. 즉, DFS 알고리즘을 두 번 반복한다.
같은 알고리즘을 반복하는 경우, 여러 번 사용하는 변수들 초기화를 빠뜨리지 않도록 주의한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int main() {
// input
cin >> V;
for (int i = 0; i < V; i++) {
int node;
cin >> node;
while (true) {
int next_node, weight;
cin >> next_node;
if (next_node == -1) break;
else {
cin >> weight;
}
graph[node].push_back({ next_node, weight });
}
}
// find farthest node from node 1
dfs(1, 0);
// initialize
max_weight = 0;
memset(visited, 0, sizeof(visited));
// find tree's diagonal
dfs(farthest_node, 0);
cout << max_weight;
}
void dfs(int node, int weight)
일반적인 dfs의 구현과 같다. 가장 먼 노드를 찾아야 하므로, dfs 함수 내에서 max_weight, farthest_node 변수를 이용해 기록한다.
✅ 답이 잘못 나와서 dfs 함수에서 node, weight를 출력했는데 weight가 이상하다면, 다음 노드를 탐색할 때 현재 weight에 다음 노드의 weight를 더했는지 확인하자.
dfs(next_node, **weight + next_weight**);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs(int node, int weight) {
// find farthest node
if (weight > max_weight) {
max_weight = weight;
farthest_node = node;
}
// visit check
visited[node] = true;
// next node
for (int i = 0; i < graph[node].size(); i++) {
int next_node = graph[node][i].first;
int next_weight = graph[node][i].second;
if (visited[next_node] == 1) continue;
else {
dfs(next_node, weight + next_weight);
}
}
}