JUNGOL #6247 최소리프노드 c++

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

 

 

간단한 문제일 수록 발상의 전환이 매우 중요하다는 것을 깨닫게 해준 문제인 것 같다.

 

문제

N개의 노드로 이루어진 트리가 있다. 여기서 트리의 리프노드의 개수가 최소가 되도록 K개의 리프노드를 제거하였을 때, 최소리프노드의 값을 구해야 하는 문제이다.

 

제한 : (0 <= K < N < 10^6)

 

시도 + 접근

 

1. 문제상황 관찰

문제에서 요구하는 것이 '리프노드 개수 최소화'이므로 리프노드의 개수가 줄어드는 상황에 대해서 생각해보자.

일직선 방향으로 이어지는(진출차수가 1인) 편향 서브 트리에서는 노드를 제거하여도 리프노드의 개수가 줄어들지 않는다.

노드를 삭제하면 그의 부모노드가 루트노드가 되어버리기 때문이다. 

 

때문에, 2개 이상의 자식을 가진 노드에서 하나의 자식을 삭제하였을 때만 리프노드의 개수가 줄어들 수 있다.

 

2. 여러가지 시도

- 첫번째 시도 

 

리프노드를 하나의 '잔가지'들로 생각하고, 최대한 길이가 짧은 잔가지 부터 쳐내야 겠다는 생각을 했다. 즉, 분기점으로부터 떨어진 거리가 가장 짧은 노드들을 차례로 삭제해나간다는 것이다. 하지만 트리의 잔가지를 쳐낸 후 변동된 정보를 다른 모든 잔가지들에 대해 업데이트해주는 방법을 생각해내지 못해 결국 다른 풀이를 시도하였다.

 

첫번째 시도를 할 당시의 머릿속

 

(이 풀이를 생각할 당시에는 '서브트리의 크기' 또한 삭제에 영향을 준다고 생각하고 있었기에, 자식노드의 수를 제외하고는 업데이트해줄 필요가 없다는 점을 모르고 있었다. 위 그림과 같이 리프노드가 아닌 노드를 기준으로 삭제를 위한 연산의 횟수를 구하려 했다. 범위를 리프노드와 분기점 만으로 축소하면 된다는 생각을 못했다.

지금 생각해보면, 이 풀이에서 리프노드들의 삭제 비용을 모두 pq에 넣고, 삭제 시켜가며 삭제로 인해 새롭게 생겨나는 리프노드들만 다시 pq에 넣어주면 되는 것이었다.)

 

- 두번째 시도

 

반대로 트리의 리프노드에서부터 시작해 bfs를 돌려 정점을 하나 하나씩 삭제해가는 방식도 생각해보았다. 자식의 수가 0이 될 때 마다 새롭게 큐에 넣어주는 방식을 통해, 깊이별로 탐색하여 k번의 제거 내에 최대한 많은 리프노드를 제거한다는 전략이었지만, 당연히도 이는 전체에서 최적이 보장되지 않았고, 또다른 풀이를 생각해내야 했다.

 

- 세번째 시도

 

첫번째 시도에서 조금 더 발전된 풀이이다. 만약 '잔가지'들을 쳐내며 트리의 정보를 업데이트하는 것이 불편하다면, k개 제거 후 최종적으로 남아있는 '굵은 가지'들을 찾아내면 되지 않을까?? 라는 생각에서 비롯되었다.

 

추상적인 생각을 조금 더 구체화해보려 했다.

원래 트리에서 우리가 제거하고 싶었던 서브트리들은 모두 분기점으로 부터의 깊이가 얕은 것들이었다. 

제거하는데에 비용이 덜 들기도 하지만, 리프노드가 적어야 한다는 조건상 '불리하기' 때문이었다.

 

제한된 노드로 가장 리프노드가 적은 트리를 만들기 위해서는 분기점의 개수가 반드시 적어야 한다.

 

즉, 분기점으로 부터 리프노드까지 하나로 이어지는 '굵은가지'가 많을 수록 좋다는 것이다.

 

기본적으로 트리는 n-k개 이상의 노드로 만들어져야 한다. 

 

때문에, 문제를 제한된 노드 개수 내에서 리프노드의 개수를 최소화하는 것이라면, 분기점으로 부터 가장 깊이 내려가는 가지들만 선택하여 n-k개의 노드를 채우면 되는 것이다.

 

이는 dfs로 각 노드의 리프노드에 도달하기까지의 '최장거리'를 저장한 후, 분기점에서 갈라지는 여러 '가닥'들을 배열에 저장하여, 정렬한 후, 깊이가 깊은 것 부터 순회하며 n-k개의 노드를 채울 때까지 가닥, 즉 리프노드의 수를 증가시키면 되는 것이다.

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> child;
vector<int> maxd, ans;
void dfs(int cur) {
	int subd = 0;
	for(int c: child[cur]) {
		dfs(c);
		subd = max(subd, maxd[c]);
	}
	maxd[cur] = subd + 1;
}
void dfs2(int cur, bool big) {
	if(!big)ans.push_back(maxd[cur]);
	int maxchild, maxdepth = 0;
	if(!child[cur].size())return;
	for(int c: child[cur]) {
		if(maxdepth < maxd[c]) {
			maxchild = c;
			maxdepth = maxd[c];
		}
	}
	dfs2(maxchild, true);
	for(int c: child[cur]) {
		if(c!=maxchild) {
			dfs2(c, false);
		}
	}
}

int main() {
	int n, k, leaf = 0, num = 0;
	cin >> n >> k;
	child.resize(n+1);
	maxd.resize(n+1, 1);
	for(int i = 1; i < n; i++) {
		int x;
		cin >> x;
		child[x].push_back(i);
	}
	dfs(0);
	dfs2(0, false);
	sort(ans.begin(), ans.end());
	int r = n-k;
	for(int i = ans.size()-1; i >= 0; i--) {
		r -= ans[i];
		num++;
		if(r <= 0)break;
	}
	cout << num;
}

 

 

지우는 것들을 찾는 것이 아니라, 최종적으로 남아있는 값을 기준으로 생각해볼 수도 있다는 것을 배운 문제였던 것 같다. dfs를 오랜만에 짜보는 것 같기도 한 것 같다. 그래프 문제도 꾸준히 풀어보겠다.