백준 1967 : 트리의 지름

www.acmicpc.net/problem/1967

1967번: 트리의 지름

이 문제는 트리의 최대 지름을 구하는 문제이다. 모든 노드 간의 거리를 확인해야한다는 점에서 플로이드워셜 알고리즘이나 다익스트라를 노드 수 n번만큼 돌리는 방법이 생각났지만 각각 시간복잡도가 O(n^3), O(n * n * (n-1)) -> O(n^3) 으로 무조건 시간초과가 나므로 사용할 수 없다. 이후 최소공통조상(LCA)을 구해서 공통조상 노드에서 각각의 노드까지의 거리의 합을 구해주려고 하였으나 이 경우도 모든 노드에서 모든 노드로 O(n^2), LCA O(logN)의 시간복잡도를 가지므로 시간복잡도 O(n^2 * logN)를 가지므로 사용 불가능하다. 그래도 여기서 아이디어를 얻어서 다음과 같은 방법으로 문제를 해결했다.

루트노드부터 간선을 따라 재귀적인 방법으로 자식노드로 내려가면서 각각의 자식노드를 루트노드로 하는 서브트리에서 루트 -> 각각의 리프노드까지의 거리를 sub_tree_cost 라는 배열에 벡터로 push_back 해준다. 그 후 sub_tree_cost의 해당 인덱스에 존재하는 벡터의 사이즈가 1보다 크다면 내림차순으로 정렬해주어 제일 큰 두개의 수를 더해서 거리가 가장 먼 경우인지 확인해준다. 해당 노드에서 가지가 하나밖에 없을 시 서브트리의 루트노드와 리프노드 간의 거리가 가장 먼 경우가 되는지 확인해준다. 코드는 다음과 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, max_val;
vector<pair<int,int>> child[10001];
vector<int> sub_tree_cost[10001];

int dfs(int parent_node) {
	// 자식 없을 시 0 return
	if (!child[parent_node].size()) return 0;
	// 해당 노드가 이미 한 번 dfs를 돌아서 메모제이션 되어있을 시 그 값 사용
	if (sub_tree_cost[parent_node].size()) return sub_tree_cost[parent_node][0];
	// 모든 자식들에 대하여
	for (int i = 0; i < child[parent_node].size(); i++) {
		// 자식이 리프노드일 때 까지 재귀호출 -> 
		// 재귀 빠져나오면 리턴값(간선 가중치 합)에 해당 자식노드의 간선 가중치 더해서 parent_node를 루트로 하는 서브트리의 코스트에 추가
		sub_tree_cost[parent_node].emplace_back(dfs(child[parent_node][i].first) + child[parent_node][i].second);
	}
	// 서브트리에 간선의 개수가 1개 초과일 시 정렬 후 제일 큰 두개의 가지의 하위 노드 간선 가중치 합의 합을 max_val과 비교, 갱신
	if (sub_tree_cost[parent_node].size() > 1) {
		sort(sub_tree_cost[parent_node].begin(), sub_tree_cost[parent_node].end(), [](const int a, const int b) { return a > b; });
		max_val = max(max_val, sub_tree_cost[parent_node][0] + sub_tree_cost[parent_node][1]);
	}
	else if (sub_tree_cost[parent_node].size() == 1) max_val = max(max_val, sub_tree_cost[parent_node][0]);
	// 해당 노드를 루트로 하는 서브트리의 각각의 간선에 대한 하위 노드 간선 가중치 합들 중 가장 큰 값을 리턴
	return sub_tree_cost[parent_node][0];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int parent_node, child_node, cost;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> parent_node >> child_node >> cost;
		child[parent_node].emplace_back(child_node, cost);
	}
	dfs(1);
	cout << max_val;
	return 0;
}

재귀적인 방법을 사용하기 때문에 메모제이션 기법을 사용하여 최대한 비효율적인 부분을 줄이려고 노력했다.  n이 최대 10000이라 최악의 경우 재귀 호출이 10000번 일어날 수도 있기 때문에 재귀적으로 코드를 구현하고나서 비재귀적으로 바꾸려고 시도하였으나 도저히 방법을 모르겠어서 포기했다. 이 부분은 나중에라도 더 생각해보면 좋을 것 같다.

 

추가로 문제를 풀고 나서 찾아보니 이 문제는 bfs를 두 번 돌려서 풀 수도 있다. 이 방법이 더 깔끔하고 효율적인 것 같다. 왜 bfs 두 번으로 트리의 지름을 구할 수 있는지는 아래에 링크에 잘 설명되어 있으니 참고 바란다.

 

blog.naver.com/jinhan814/222084804068

[BOJ] 1967번 - 트리의 지름

 

메모리: 3644 kb

시간: 4 ms