[Baekjoon] 1167번: 트리의 지름

🥅 문제

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

 

🔍 설계

가지가 1인 노드들에서 dfs를 이용하여 트리의 지름을 구하려고 했는데, 시간 초과가 발생하였다. 도저히 해결방법을 모르겠어서 레퍼런스 블로그를 참고하였다.

 

임의의 노드에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드를 구하면, 트리의 지름을 구할 수 있다고 한다.

어떻게 이런 결과가 나오는지 공부해본다.

 

임의의 노드를 x라고 하고, x에서 가장 먼 노드를 y라고 하면, 3가지 경우가 있다.

1) x가 트리의 지름의 양 끝 점 중 하나라면, x에서 가장 먼 노드인 y가 나머지 끝 점 중 하나가 되므로 y에서 가장 먼 노드(x)까지의 거리는 트리의 지름이 된다.

2) y가 트리의 지름의 양 끝 점 중 하나라면, 당연하게 y에서 가장 먼 노드까지의 거리가 트리의 지름이 된다.

3) y가 트리의 지름과 상관없고, 아래 그림과 같이 트리의 지름은 u-v이고, x-y와 u-v가 교차점 t를 가진다고 하자. x에서 가장 먼 노드가 y라고 했는데, 이는 모순이다. x에서 가장 먼 노드까지의 경로는 트리의 지름을 구성하는 x-t-u 또는 x-t-v가 되어야 할 것이다. y가 가장 먼 노드라면, 트리의 지름은 u-t-y 또는 v-t-y가 되어야 한다. 하지만, y는 트리의 지름과 상관없다고 가정했으므로 모순이다.

위 조건을 유지하면서 만약 교차점이 없는 경우, 그건 트리가 아니다.

 

따라서 결론은 y는 트리의 지름을 이루는 양 끝 점 중 하나일 수 밖에 없다.

 

👊 풀이

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

int v, start, endd, cost, max_node, result = 0;
vector<vector<pair<int, int>>> adj_list(100001);
vector<bool> visited(100001,false);

void dfs(int cur_node, int cur_cost) {
	if (result < cur_cost) {
		result = cur_cost;
		max_node = cur_node;
	}

	for (int i = 0; i < adj_list[cur_node].size(); i++) {
		int next_node = adj_list[cur_node][i].first;
		int next_cost = adj_list[cur_node][i].second;
		if (!visited[next_node]) {
			visited[next_node] = true;
			dfs(next_node, cur_cost + next_cost);
			visited[next_node] = false;
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> v;
	for (int i = 0; i < v; i++) {
		cin >> start;
		while (true) {
			cin >> endd;
			if (endd == -1) {
				break;
			}
			cin >> cost;
			adj_list[start].push_back({ endd, cost });
		}
	}

	visited[1] = true;
	dfs(1, 0);
	visited[1] = false;

	visited[max_node] = true;
	dfs(max_node, 0);
	visited[max_node] = false;
	
	cout << result << "\n";

	return 0;
}

 

📖 레퍼런스

https://blog.myungwoo.kr/112

트리의 지름 구하기

 

https://blogshine.tistory.com/111

[알고리즘] 트리의 지름 : Diameter of Tree