[백준/C++] 트리의 지름 (No. 1167)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

사실 이 문제는 문제의 제목이 가장 큰 힌트라고 생각한다.

 

목표는 트리의 지름을 구하는 것으로 트리의 지름은 트리에서 임의의 두 점 사이의 거리가 가장 긴 것을 의미한다.

 

그렇다면 어떻게 그 거리를 구하기 위해 생각해야할 점은 2개다.

 

1. 특정 두 점 사이의 거리가 가장 먼 경우는 두 점이 전부 최하위에 있는 leaf다.

2. 두 점 사이의 거리가 가장 먼 노드를 구했을 때, 정점을 a, b라고 하면 임의의 정점 c는 a, b 의 경로에 포함되거나 포함되지 않는다.

 

1번은 당연한 말이다.

왜냐하면 두 정점이 leaf가 아니면 그 하위에 노드가 있으므로 더 긴 정점이 존재하게 되고, 가장 긴 거리라는 가정에 위배되기 때문이다.

 

2번도 당연한 말이지만,  아래 그림에서 구분한 이유를 아래에서 설명하겠다.

 

 

먼저 임의의 정점을 선택해 최 상단 노드로 결정하고 트리를 그린다.

이후 트리를 그려나가면서 하위 자식들 중 거리가 먼 자식을 2개 선택하면서 가장 거리가 먼 노드를 구하면 된다.

 

예를 들어 아래의 S가 현재 탐색 중인 노드이고 1, 2, 3은 자식 노드라고 생각해 보자.

이때, 현재 노드가 S이므로  S의 상단에 있는 부모 노드인 A 노드는 가장 긴 거리를 만드는데 포함되지 않는 노드라고 생각하고 가장 긴 거리를 구하는 것이다.

(A노드가 포함된 가장 긴 거리는 A를 탐색할 때 구하므로 S에서 고려하지 않아도 된다는 뜻)

 

이렇게 S를 탐색할 때 A노드 부분을 고려하지 않음으로써 중복 탐색을 고려하지 않기 위해 2번 조건을 생각한 것이다.

이제 S를 기준 즉, 중심으로 한 가장 긴 거리를 구해보자.

 

먼저 S를 기준으로 1의 경로에 있는 가장 긴 거리, 2의 경로에 있는 가장 긴 거리, 3의 경로에 있는 가장 긴 거리를 구한다.

 

여기서 2의 경로에 있는 가장 긴 거리를 구하는 방법은 마찬가지로 하위에 있는 4, 5 노드의 거리를 비교하면 된다.

(즉, 비용 a와 b 중 어떤 값이 더 큰 값을 S에 return해주면 그게 S의 자식인 2 경로에 있는 가장 긴 거리다)

 

그러면 S를 기준으로 자식 노드의 경로에 있는 거리들을 전부 계산했다고 가정하자. (이 때, a가 b보다 길다고 가정)

 

그러면 계산된 자식 노드의 거리인 (c, d, e+a) 중 긴 것을 2개 뽑아서 더하면 S를 중심으로 하는 가장 긴 경로의 계산이 끝난다.

 

(초록색 부분에 대한 가장 긴 거리의 계산이 끝났다는 뜻) 

이제 계산이 끝났으므로 S는 A에 가장 긴 경로를 return해주면 된다.

(2번 노드에서 a를 return해준 것과 같다)

 

즉, 최상단 노드인 A에서 탐색을 시작 했으므로, A를 중심으로 하는 가장 긴 거리도 구하기 위해서 S의 탐색이 끝나면 A에 가장 긴 경로를 return 해주는 것이다.

 

(만약 S 하위에 있는 두 점이 정답이 되는 경우라면 이미 S를 탐색할 때 계산이 된 상태다.)

 

이렇게 자식 노드를 탐색해 나가면서 부모노드는 포함하지 않으면서 자식 노드를 포함한 경우에 대한 가장 긴 거리를 구해 나가면 된다.

 

특정 정점에 방문했을 때, 하위의 자식 노드 중 거리가 긴 것을 두 개 선택해 비교하는게 특정 정점이 트리 지름의 중심이 되는 모습처럼 보였다.

그렇기 때문에 이 문제의 이름이 가장 큰 힌트라고 생각했던 이유다.

 

위 방법을 따라 최상단 노드부터 탐색을 시작해 가장 거리가 긴 경우를 출력하면 문제가 해결된다.

 

 

 

​

[아이디어 정리]

1. 임의의 정점을 최상단 노드로 정하고 트리를 그린다.
2. 트리를 그려나가면서 현재 노드는 포함하지만 상단 노드는 경로에 포함하지 않는 경우에 대한 두 정점 사이의 가장 긴 거리를 구한다.
3. 거리의 계산이 끝나면 부모 노드에 현재 노드의 하위 경로 중 가장 긴 경로를 return한다.
4. 마찬가지로 부모노드의 차례가 되면 그 노드를 포함하지만 상위 노드는 포함하지 않는 경우에 대해 가장 긴 거리를 구한다.
5. 최종적으로 구해진 가장 긴 거리를 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
using namespace std;

int maxD = 0;
int DCalc(vector<int> &parents, vector<vector<pair<int, int>>> &graph, int nowN)
{
	int max1 = 0, max2 = 0, tmp;
	for (int i=0; i<graph[nowN].size(); i++)
	{
		if (parents[nowN]!=graph[nowN][i].first)
		{
			parents[graph[nowN][i].first] = nowN;
			tmp=DCalc(parents, graph, graph[nowN][i].first)+ graph[nowN][i].second;
			if (tmp >= max1) {
				max2 = max1;
				max1 = tmp;
			}
			else if (tmp > max2) {
				max2 = tmp;
			}
		}
	}
	maxD = max(maxD, max1 + max2);
	return max1;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<vector<pair<int, int>>>graph(n + 1);
	int a, b, c;
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		while (true)
		{
			cin >> b;
			if (b>0)
			{
				cin >> c;
				graph[a].push_back(make_pair(b, c));
			}
			else {
				break;
			}
		}
	}
	vector<int> parents(n + 1, 0);
	DCalc(parents, graph, 1);
	cout << maxD;

	return 0;
}

 

---

문제의 제목 덕분에 매우 쉽게 풀린 문제였다

 

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