문제
풀이
dfs 를 활용하는 문제이다.
우선 임의의 정점에서 가장 거리가 먼 정점을 찾는다. 나는 임의의 정점을 1로 선택했다.
찾은 정점에서 다시 dfs를 수행하여 거리가 가장 먼 정점을 찾고, 그 정점까지의 거리가 트리의 지름이다. 아래 그림을 통해 확인해보자.
우선 임의의 정점 1에서 가장 거리가 먼 정점은 11의 거리를 갖는 5인 것을 알 수 있다. 다시 이 정점 5에서 가장 거리가 먼 정점을 찾으면 정점 1이고 거리는 11이므로 답은 11이 된다.
그렇다면 임의의 정점 2로 확인해보자.
가장 거리가 먼 정점은 10의 거리를 갖는 5이다. 다시 5에서 가장 거리가 먼 정점을 찾으면 11의 거리를 갖는 1이고 답은 11이 된다.
위와 같이 두번의 dfs에서, 첫번째 dfs는 가장 바깥에 있는 정점을 찾는 것으로 이해 할 수 있다. 그 후 첫번째 dfs를 통해 찾은 정점에서 두번째 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
// vector의 자료형을 위한 구조체 정의
struct Node
{
int index;
int dist;
};
int v, maxDist, maxNode;
bool visit[100001]; // 방문확인
vector<Node> graph[100001];
void dfs(int node, int dist)
{
// 방문한 노드면 return
if (visit[node])
return;
// maxDist 갱신
if (maxDist < dist)
{
maxDist = dist;
maxNode = node;
}
visit[node] = true; //방문 체크
// 현재 정점에서 연결 된 정점들로 dfs 수행
for (int i = 0; i < graph[node].size(); i++)
{
int nextIndex = graph[node][i].index;
int nextDist = graph[node][i].dist;
dfs(nextIndex, nextDist + dist);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> v;
int fr, to, dist;
for (int i = 1; i < v + 1; i++)
{
cin >> fr;
while (true)
{
cin >> to;
if (to == -1)
break;
cin >> dist;
graph[fr].push_back({to, dist});
graph[to].push_back({fr, dist});
}
}
// 임의의 정점 1에서 가장 거리가 먼 정점 찾기
dfs(1, 0);
memset(visit, 0, sizeof(visit));
maxDist = 0;
// 1과 가장 먼 정점에서 다시 dfs 수행하여 트리의 지름 찾기
dfs(maxNode, 0);
cout << maxDist << '\n';
return 0;
}
