[백준] 1167번 트리의 지름 [C++]

https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

---

문제

---

접근 방법

트리의 지름이란 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 먼저 이 두 점을 찾기위해서는 임의의 한 점에서 DFS를 해서 가장 멀리 있는 점을 찾아낸다. 그 점은, 내가 처음에 임의로 지정한 점이 지름에 포함되어있든, 아니든 지정한 점으로부터 가장 먼 거리에 있기 때문에, 트리의 지름에 포함된 점이라고 할 수있다.

이렇게 찾아낸 점에서 부터 다시 DFS를 해서 거리가 가장 먼 점을 찾아내면, 그 점 또한 트리의 지름에 포함되어 있다.

이렇게 발견한 두 가지 점의 거리가 바로 트리의 지름의 길이다.

 

---

코드

#include<iostream>
#include<cmath>
using namespace std;
int n;
vector<pair<int, int>> con[100001];
bool flag[100001];
int dis[100001];
void dfs(int a) {
	flag[a] = true;
	for (int i = 0; i < con[a].size(); i++) {
		if (flag[con[a][i].first] == false)
		{
			dis[con[a][i].first] = dis[a] + con[a][i].second;
			dfs(con[a][i].first);
		}
	}

}
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	int x, y, d;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		while (y != -1) {
			cin >> d;
			con[x].push_back({ y,d });
			con[y].push_back({ x,d });
			cin >> y;
		}

	}
	for (int i = 1; i <= n; i++) {
		flag[i] = false;
	}
	int maxD = 0;
	int maxN = 0;
	dis[1] = 0; //임의의 점을 1번 노드로 지정

	dfs(1);
	for (int i = 1; i <= n; i++) {
		if (dis[i] > maxD) {
			maxD = dis[i];
			maxN = i; 
		}
	}//maxN값이 바로 1번노드로부터 가장 멀리 떨어진 노드
	for (int i = 1; i <= n; i++) {
		flag[i] = false;
		dis[i] = 0;
	}
	dfs(maxN); //maxN에서 다시 모든 노드까지 거리를 잰다.
	for (int i = 1; i <= n; i++) {
		if (dis[i] > maxD) {
			maxD = dis[i];//모든 노드중에 가장 멀리있는 노드까지의 길이가 트리의 지름
		}
	} 
	cout << maxD;

}

---

저번 학기 학교 수업때 유사한 문제가 나왔었는데, 그 때 못 풀고 해설을 듣고 풀이에 감탄을 했던 기억이 있다.

아무 노드로부터 시작해서 가장 멀리있는 점이 트리의 지름의 두 점중 하나가 된다는 사실을 알면 쉽게 풀 수 있고, 모르면 많이 해매게 될 것 같다.