백준 1967(트리의 지름) dp

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

1967번: 트리의 지름

 

dp로 풀 수 있다길래 dp로 풀어보았다. 

 

dp의 핵심은 항상 생각하는 것이다. 전체의 부분이 빠짐없이 되는 부분을 찾으면 된다. 

 

그래서 나는 

 

dp[node]를 dp[node][2]로 쪼개어서, 

 

dp[node][0]은 node를 root로 하는 트리의 지름

dp[node][1]은 node를 root로 하는 최대 간선 길이 

 

로 하였다. 

 

dp[node][1]의 존재 이유는 더 상위 tree의 지름을 구할 때 필요해서 선언해주었다.

 

 

 

그리고 함수는 탑다운형식으로 서브트리부터 root까지 오는 방식으로 구현하였다. 

 

 

dp[node][0]은 서브트리 중에서 max{ 서브트리의 지름, (가장 큰 (서브트리의 간선 + 두 노드를 잇는 간선의 길이) + 두 번째로 큰 (서브트리의 간선 + 두 노드를 잇는 간선의 길이)) } 로 설정할 수 있었고, 

 

dp[node][1]은 max{ 서브트리의 간선 + 두 노드를 잇는 간선의 길이} 로 설정할 수 있었다. 

 

위 코드에서 알 수 있듯이 

dp[node][0]은 dp[node][1]을 사용한다. 

 

그래서 dp[node][0] 코드를 더 뒤에 배치하였다. 

 

 

 

void solve(int root) {
	for (int i = 0; i < tree[root].size(); i++) {
		solve(tree[root][i]);
	}
	sec = dp[root][1] + parent[root].second;
	if (dp[parent[root].first][1] < dp[root][1] + parent[root].second) {
		sec = dp[parent[root].first][1];
		dp[parent[root].first][1] = dp[root][1] + parent[root].second;
	}
	dp[parent[root].first][0] = max({ dp[parent[root].first][0], dp[root][0], dp[parent[root].first][1] + sec });
}

 

 

이 코드는 모든 자식을 돌고 상위 노드로 간다. 

 

처음에는 부모에서 자식노드의 간선값까지 저장했으나, 그렇게 되면 탑다운 방식으로는 구현하기가 너무 힘들었다.

따라서 자식들로 부모노드를 구현해야 하므로 parent 배열에 간선값까지 설정해서 구현하였다. 

 

sec에는 만약 간선이 하나일 경우에는 그 간선을 저장, 두 개 이상일 경우에는 두번째로 큰 간선의 값을 저장하게끔 하였다. 

 

dp[node][0] := node를 root로 하는 트리의 지름

의 코드는 

 

(어떤 자식의 트리의 지름 vs 자식의 간선 길이 + 두 점을 잇는 간선)

 

을 모든 자식에 대해서 가장 큰 값을 저장하게끔 코드를 구현하였다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 10001

int n, a, b, c, sec;
int dp[MAX][2];
vector<pair<int, int> > parent(MAX);
vector<int> tree[MAX];

void solve(int root) {
	for (int i = 0; i < tree[root].size(); i++) {
		solve(tree[root][i]);
	}
	sec = dp[root][1] + parent[root].second;
	if (dp[parent[root].first][1] < dp[root][1] + parent[root].second) {
		sec = dp[parent[root].first][1];
		dp[parent[root].first][1] = dp[root][1] + parent[root].second;
	}
	dp[parent[root].first][0] = max({ dp[parent[root].first][0], dp[root][0], dp[parent[root].first][1] + sec });
}

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

	cin >> n;
	for (int i = 0; i < n-1; i++) {
		cin >> a >> b >> c;
		tree[a].push_back(b);
		parent[b] = make_pair(a, c);
	}
	parent[1] = make_pair(0, 0);
	solve(1);
	cout << max(dp[1][0], dp[1][1]) << "\n";
}

 

dp에 대한 확신은 있었고 하지만 아직까지 구현도 좀 어렵고 사고하는 것도 어려운 것 같다.