JUNGOL #5652 주유소 && #2574 사회망 서비스(복습)

https://jungol.co.kr/problem/5652

 

문제

 

N개의 노드로 이루어진 트리가 있다. 이 트리의 각 노드에 주유소를 적절히 설치하여 트리 내에서 길이가 K인 모든 경로에 대해서

주유소가 없는 길이 없도록 하려 한다. 이때, 설치해야 하는 주유소의 개수의 최솟값을 구하시오.

(단, 경로의 길이란 처음 노드와 끝 노드를 잇는 간선의 개수를 의미한다.)

 

(2 <= N < 200000, 1 <= K < N-1)

 

 

문제 관찰

문제를 관찰해보니 문제 전체의 느낌이 사회망 서비스와 매우 비슷하게 느껴졌다.

단지 다른 점은 주유소의 경우에는 트리 내에서 길이가 K인 모든 경로에서 주유소가 포함되어야 하는 반면, 사회망서비스는 길이가 1인 경로로 연결된 노드들 중에서 하나만 얼리어답터여도 된다는 점 정도이다.

 

사회망서비스에서 문제를 어떻게 해결했는지 떠올려봤다.

리프노드까지 타고 내려간 후, 깊은 곳에서 부터 자식노드들 중에서  얼리어답터가 아닌 노드가 단 하나라도 있다면 부모노드를 얼리 어답터로 만드는 그리디 방식을 채택했었다.

 

이는 자식노드를 루트로 하는 서브트리들이 모두 최소 개수로 완전한 사회망서비스를 이루고 있다는 전제를 하였기에 가능한 전략이었다.

 

주유소에서도 K = 1일때의 경우를 생각해보자.

마찬가지로 어떤 노드를 검사할 때 자식노드를 루트로 하는 서브트리들이 모두 주유소로 완전연결되었다는 점을 보장하기 위해 리프노드에서 부터 시작해야 할 것이다.

 

서브트리들에서 길이 K인 경로 중 주유소가 포함되지 않는 경로가 없다고 가정했기 때문에, 현재 노드를 기준으로 주유소가 포함되지 않은 경로가 있을 수 있는 상황은 다음과 같다.

 

서브트리 2개(또는 1개)의 최대깊이 + 1 > K일때

 

 

서브트리에서 주유소가 없는 길이 K인 경로가 없다고 하더라도 이를 제외한 가장 긴 경로는 존재할 것이다.

현재 노드의 자식 노드들 중에서 이 길이가 가장 긴 2개를 현재 노드와 이어 경로를 만들면, 이는 트리의 지름이 된다.

 

이 트리의 지름이 K보다 크다면 우리는 반드시 현재 노드를 주유소로 만들어야 할 것이다.

 

하지만 이 과정을 떠올리면서 더 간단한 발상이 떠올랐다.

 

"주유소 노드는 그냥 트리에서 잘라내면  처리가 편하지 않을까?" 라는 생각...

 

처음에는 트리의 지름이 k보다 크지 않을 때까지는 주유소 노드가 없을 것이다.

k보다 커지는 순간 현재노드를 처음으로 주유소로 만들 것이다.

 

때문에, 이후 더 레벨이 높은 노드에서 해당 서브트리를 포함하는 경로를 고려한다고 했을 때 루트노드인 주유소가 반드시 포함될 것이다. 

때문에, 이제 해당 서브트리를 포함하는 경로 중 조건을 만족하지 않는 경로는 존재하지 않는다. 

 

때문에, 그냥 주유소로 배정된 순간, 그 노드를 루트로 하는 트리를 전체 트리에서 잘라낸다고 생각하는 것이다.

 

이렇게 되면, 깊은 곳부터 계산하기에, 상위 레벨에서 트리의 최대 깊이를 참조할 때 수정된 깊이가 반영될 것이고, 최종적으로 

주유소를 칠한 최소 개수를 구할 수 있게 되는 것이다.

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> md, occ;
int n, k, ans;
void dfs(int p, int cur) {
	for(int c: g[cur]) {
		if(c==p)continue;
		dfs(cur, c);
	}
	priority_queue<int> pq;
	for(int i = 0; i < 3; i++)pq.push(0);
	for(int c: g[cur]) {
		if(c == p || occ[c])continue;
		pq.push(md[c]);
	}
	md[cur] = pq.top() + 1;
	pq.pop();
	if(md[cur] + pq.top() > k) {
		occ[cur] = 1;
		ans++;
	}
}

int main() {
	cin >> n >> k;
	g.resize(n+1);
	md.resize(n+1, 1);
	occ.resize(n+1, 0);
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(-1, 1);
	cout << ans;
}

 

 

추가로 예전에 작성한 사회망 서비스 코드를 조금 더 간단하게 다시 짜봤다. (이제보니까 dp가 아니라 그냥 그리디인 것 같기도..?)

 

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> a;
int ans;
void dfs(int p, int cur) {
	for(int c: g[cur]) {
		if(c==p)continue;
		dfs(cur, c);
	}
	for(int c: g[cur]) {
		if(c==p)continue;
		if(!a[c]) {
			ans++;
			a[cur] = 1;
			return;
		}
	}
}

int main() {
	int n;
	cin >> n;
	g.resize(n+1);
	a.resize(n+1, 0);
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(-1, 1);
	cout << ans;
}

 

 

이제야 트리를 다루는 방법을 조금이나마 알 것 같다. 공부할 수록 재귀로 푸는 트리 문제는 분할정복이랑 매우 비슷한 것 같다..