BOJ7812 중앙 트리

7812번 중앙트리

트리와 각 간선의 가중치가 주어질 때

한 꼭짓점에 대해 모든 꼭짓점과의 거리 합이 최소일 때의 그 값을 구한다.

즉 중앙 정점과 모든 꼭짓점과의 거리 합을 구한다.

 

 

DFS, DP

당연히 모든 점에 대해 거리를 다 계산해볼 순 없고

트리이므로 DFS,

중앙 정점이 될 수 있는 점을 DP로 찾아가며 푼다.

 

처음에 DFS 두 번에 푸는 방법으로 해결했는데, 한 번만으로도 충분했다.

일단 간선은 벡터 E에 간선을 { 자식 노드 , 가중치 } 로 저장한다.

---

DFS 두 번 하는 방법: 트리 먼저 만들고, 중심을 옮길지 말지 결정

 

0을 기준으로 모든 정점의 거리 합을 계산한 후

0보다 하위인 정점이 중앙 정점이 될 수 있는지 판단

 

 

 

1. 0에서 DFS, 모든 정점과 0사이의 거리 합 계산

이때 각 정점에 달린 자식 노드 수(자기 자신 포함, 자기 자신보다 하위인 노드 수)를 알아야 한다.

 

위 트리에서 간선[0-1]의 가중치는 6번을 더해야 하고, 1에 달린 자식 노드 수가 6이다.

마찬가지로 간선[1-3]의 가중치는 3번 더해야 하고, 3에 달린 자식 노드 수가 3이다.

 

long long dfs_tree(int cur) {
	vis[cur] = true;
	int child_num = 1;
	long long dist = 0;
    
	for (pii e : E[cur]) {
		int nxt = e.first;
		if (vis[nxt]) continue;

		int distnxt = dfs_tree(nxt);
		child_num += cnum[nxt];
		dist += (1LL * e.second * cnum[nxt] + distnxt);
	}
	
	vis[cur] = false;
	cnum[cur] = child_num;
	return dist;
}

child_num    cur에 달린 자식의 수 → cnum[cur]  

dist               cur의 모든 자식 노드에서 cur까지의 거리 합

 

 

 

2. 0에서 DFS, 0보다 하위인 정점이 중앙 정점이 될 수 있는지 확인

 

위 트리에서 기준 정점을 0으로 생각하면 간선[0-1]의 가중치를 6번 더해야 하고, 총 거리 합은 56이다.

0의 자식 노드인 1로 기준 정점을 옮긴다면

간선[0-1]의 가중치를 1(=7-6)번만 더해주면 된다는 사실을 알 수 있다.

즉 기존에 구한 거리 합에서 간선[0-1]의 가중치를 5번 빼준 31이 거리 합이 된다.

따라서 0보다는 1이 중앙 정점이 될 확률이 높다.

 

long long dfs_dist(int cur, long long ans) {
	vis[cur] = true;
	long long rem = ans;
    
	for (pii e : E[cur]) {
		int nxt = e.first;
		if (vis[nxt]) continue;
	
		int cnt = N - (cnum[nxt] << 1);
		if (cnt > 0) continue;
		long long tmp = dfs_dist(nxt, rem + 1LL * e.second * cnt);
		ans = (ans < tmp) ? ans : tmp;
	}

	vis[cur] = false;
	return ans;
}

ans   현재까지 가장 최소인 거리 합

cnt    ans에 간선[cur-nxt]의 가중치를 더해줄 양

따라서 cnt가 음수이거나 0인 경우에만 nxt에서 dfs를 시도한다.

(nxt의 하위 노드가 중심 정점이 될 수도 있다.)

 

dfs_dist(cur,dist)는 이전 노드를 중심 정점으로 생각할 때의 거리 합이 dist일 때,

cur의 하위 노드를 모두 고려해 찾은 최소 거리 합을 return한다.

 

 

 

3. 따라서 정답은 dfs_dist( 0 , dfs_tree(0) )이다.

 

 

 

아래는 각 트리에 대해 dfs_tree, dfs_dist를 각각 시행한 과정,,

 

 

그러나 잘 생각하면 DFS 한 번만에도 풀 수 있다.

 

 

---

DFS 한 번에 끝내는 방법: 트리를 만들면서 중심이 어느 쪽인지 결정

 

굳이 0을 기준으로 값을 구하고 다시 새로운 중심 정점을 찾을 필요가 없다.

간선[cur-nxt]에 대해,

cur이나 cur의 상위 노드가 중심 정점인 경우

⇒ 간선[cur-nxt]의 가중치를 nxt 포함, nxt보다 하위인 노드 수(=dfs(nxt))만큼 더한다.

반면 nxt나 nxt의 하위 노드가 중심 정점인 경우

⇒ 간선[cur-nxt]의 가중치를 nxt보다 상위인 노드 수(=N-dfs(nxt))만큼 더한다.

 

그러니 dfs(nxt)와 N-dfs(nxt)만 고려해 간선의 가중치를 더하면 된다.

long long dfs(int cur) {
	vis[cur] = true;
	int child_num = 1;

	for (pair<int, int> e : E[cur]) {
		if (vis[e.first]) continue;

		int cnt = dfs(e.first);
		child_num += cnt;
		ANS += 1LL * e.second * ((cnt << 1) < N ? cnt : N - cnt);
		// 중앙 정점이 cur쪽인지 nxt(e.first)쪽인지 결정
	}

	vis[cur] = false;
	return child_num;
}

 

 

 

 

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

bool vis[10000];
int N;
long long ANS = 0;
vector<pair<int, int>> E[10000]; //{who,cost}
long long dfs(int cur) {
	vis[cur] = true;
	int child_num = 1;

	for (pair<int, int> e : E[cur]) {
		if (vis[e.first]) continue;

		int cnt = dfs(e.first);
		child_num += cnt;
		ANS += 1LL * e.second * ((cnt << 1) < N ? cnt : N - cnt);
	}

	vis[cur] = false;
	return child_num;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int a, b, c;
	while (1) {
		cin >> N;
		if (!N) return 0;
		for (int i = 1; i < N; ++i) {
			cin >> a >> b >> c;
			E[a].push_back({ b,c });
			E[b].push_back({ a,c });
		}
		ANS = 0; dfs(0); cout << ANS << "\n";

		for (int i = 0; i < N; ++i) E[i].clear();
	}
}

 

 

개인적으로 tree dfs문제들이 좀 어려운 듯,,, dfs적으로 생각하는 게 어렵다.

dfs함수에서 뭘 리턴해야할지 정하기가 어렵다고 하나?

각 정점 정보를 효율적으로 전달하는 것도 여러 번 시행착오 해야하고,,

점화식을 못하는 건가!