백준 1967번 - 트리의 지름

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

1967번: 트리의 지름

 

가장 먼저 생각난 풀이는 플로이드-워셜 알고리즘이었다. 그러나 플로이드 워셜의 시간복잡도는 O(N^3)이기 때문에 불가능했다. 

그래서 트리에서의 DP를 생각해보았지만 딱히 해결법이 생각나지 않았다.

가장 쉬운 방법은 모든 지점에서 dfs를 수행하는 것이다.

노드의 개수가 1만이기 때문에

O( (V + E )^2 ) = 2만 제곱 = 4천만으로, 해결이 가능하지만 이게 정해라면 이 문제는 골드가 아닐 것이다. 그래서 구글링을 해보니 역시나 다른 방법이 있었다.

 

'지름' 의 의미는 끝점과 끝점이다. 그러므로 어느 노드를 시작으로 잡던간에, 그 노드의 최대거리에 있는 노드에서 또 최대 거리를 더하면 지름이 된다. 

그림으로 보자

 

 

원의 지름은 3에서 4의 거리이다. 그렇다면 지름을 이루는 노드가 아닌 다른 노드들에게 가장 먼 거리란 당연히 지름을 이루는 경계선의 노드가 될 수 밖에 없다.

1, 2, 5, 6은 모두 4를 최대거리로 도달하게 된다.

 

즉 아무 노드나 잡고 dfs를 해서 최대 거리 노드를 구한 후, 그 노드에서 최대거리를 출력하면 2번의 dfs로 풀어낼 수 있다.

dfs는 도구이고, 지름의 성질을 파악해야하는 문제였다.

 

아이디어를 생각하지 못했다. 언제나 유연한 사고 !!

 

처음 O(N^2) 코드

 

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

vector<pair<int, int>> node[10001];
bool visited[10001];
int N;

int answer = -1;

void dfs(int nowNode, int value) {    
	visited[nowNode] = true;
	answer = max(answer, value);
	for (int i = 0; i < node[nowNode].size(); i++) {
		int next = node[nowNode][i].first;
		int cost = node[nowNode][i].second;

		if (visited[next]) continue;
		visited[next] = true;
		dfs(next, value + cost);
	}
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;

		node[a].push_back({ b,cost});
		node[b].push_back({ a,cost });
	}

	for (int i = 1; i <= N; i++) {
		dfs(i , 0);
		for (int i = 0; i <= N; i++) {
			visited[i] = false;
		}
	}

	cout << answer << '\n';
}

 

 

정해 코드

 

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

vector<pair<int, int>> node[10001];
bool visited[10001];
int N;

int answer = -1;
int boundNode = 0;
void dfs(int nowNode, int value) {
	visited[nowNode] = true;
	if (answer < value) {
		answer = value;
		boundNode = nowNode;
	}
	for (int i = 0; i < node[nowNode].size(); i++) {
		int next = node[nowNode][i].first;
		int cost = node[nowNode][i].second;

		if (visited[next]) continue;
		visited[next] = true;
		dfs(next, value + cost);
		visited[next] = false;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;

		node[a].push_back({ b,cost});
		node[b].push_back({ a,cost });
	}

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

	cout << answer << '\n';
}