백준 1167 : 트리의 지름

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

1167번: 트리의 지름

 

모든 정점에 대하여 bfs를 돌려서 거리를 확인하는 방법은 O(V^3)으로 무조건 시간 초과가 발생하기 때문에,

트리의 특성과 메모이제이션을 적극 활용해서 문제를 해결해야 한다.

탑다운 방식의 Tree DP와 메모이제이션 기법을 활용하여 O(V)의 시간복잡도로 문제를 해결했다.

 

#include <iostream>
#include <vector>

#define max(a,b) a>b?a:b
#define NODE first
#define DIST second
using namespace std;
using pii = pair<int, int>;

int n, ans, root = 1;
vector<pii> edge[100'001];
int tree_dp[100'001];

//해당 노드의 서브트리 중 가장 긴 경로를 반환하는 함수
int find_longest_path(int node, int prev) {
	//메모이제이션 되어있을 시 해당 값 리턴
	if (tree_dp[node])
		return tree_dp[node];

	//만약 리프노드라면 0 리턴
	if (node != root && edge[node].size() < 2) 
		return 0;

	//해당 노드를 루트노드로 하는 서브트리에서 
	//가장 긴 경로 두개의 경로 길이를 저장(first, second)
	int next, child_longest_path, ret, first = 0, second = 0;
	for (int i = 0; i < edge[node].size(); i++) {
		next = edge[node][i].NODE;
		//부모 노드로 역류하는 것 방지
		if (next == prev) continue;

		//자식 노드를 루트노드로 하는 서브트리의 가장 긴 경로 값을 얻기 위하여
		//find_longest_path 함수 재귀호출
		child_longest_path = edge[node][i].DIST + find_longest_path(next, node);

		//first, second값 갱신
		if (first < child_longest_path) {
			second = first;
			first = child_longest_path;
		}
		else second = max(second, child_longest_path);
	}

	//트리의 지름 갱신
	ans = max(ans, first + second);
	//현재 노드를 루트노드로 하는 서브트리의 가장 긴 경로를
	//메모이제이션 해주면서 해당 값 리턴
	return tree_dp[node] = first;
}

void solution() {
	int node1, node2, dist;
	cin >> n;

	node1 = 0;
	for (int i = 0; i < n; i++) {
		cin >> node1;
		while (1) {
			cin >> node2;
			if (node2 == -1) break;
			cin >> dist;

			edge[node1].emplace_back(node2, dist);
		}
	}
	//root노드는 어떤 노드가 되던지 상관없음
	find_longest_path(root, 0);
	cout << ans;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 8940 kb

시간: 96 ms

 

옛날에도 거의 똑같은 문제를 풀었었는데, 그 때보다 지금 풀이가 더 간단하고 메모리 측면에서도 우수한 것 같다.

https://unfunhy.tistory.com/19

백준 1967 : 트리의 지름