Codeforces Round #748 (Div. 3)-E. Gardener and Tree

문제 설명

트리는 방향이 없고 사이클이 존재하지 않는 연결된 그래프이다. 이 문제는 root 노드가 존재하지 않는 트리를 다룬다. 트리의 리프노드는 최대 1개의 노드로만 연결된 노드를 말한다.

정원사 수호는 $n$개 노드를 가진 트리를 가꾼다. 그는 트리를 다듬기로 결정했다. 트리를 다듬기 위해서 그는 몇몇 연산을 수행해야 한다. 하나의 연산에서 그는 트리에 있는 모든 리프노드를 지운다.

이 문제의 특별한 경우 몇가지가 있다.

• 빈 트리에 연산을 적용하면, 혹은 노드가 한개도 없는 트리에 연산을 적용하면 변하지 않는다.
• 한개의 노드만 남은 트리에 이 연산을 적용하면 이 노드가 사라진다.(이 노드는 리프노드로 간주된다.)
• 두 노드로 이루어진 트리에 이 연산을 적용하면 두 노드가 같이 사라진다. (두 노드 모두 리프노드로 간주한다.)

수호는 주어진 트리에 $k$번 연산을 수행한다. 남아있는 노드의 수는 몇개일까?

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t(1\le t\le {10}^4)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 트리의 노드 수와 연산의 횟수를 나타내는 두 정수 $n$과 $k(1\le n\le 4\cdot {10}^5,1\le k\le 2\cdot {10}^5)$ 가 주어진다.

다음 $n-1$개 줄에는 하나의 간선으로 연결되는 두 노드 $u$와 $v(1\le u,v\le n,u\ne v)$ 가 주어진다. 이 그래프는 트리이고, 루프가 없으며 여러개의 간선을 포함하지 않는것이 보장된다.

Output
각 테스트케이스마다 주어진 트리에 $k$번 연산을 할 때 남은 노드의 개수를 출력한다.

Example
input
6

14 1
1 2
2 3
2 4
4 5
4 6
2 7
7 8
8 9
8 10
3 11
3 12
1 13
13 14

2 200000
1 2

3 2
1 2
2 3

5 1
5 1
3 2
2 1
5 4

6 2
5 1
2 5
5 6
4 2
3 4

7 1
4 3
5 1
1 3
6 1
1 7
2 1

output
7
0
0
3
1
2

문제 접근

사용한 알고리즘: 트리, 위상정렬, 그래프, 완전탐색, 그리디 알고리즘, 구현
걸린 시간 : 00:27
사실 이 문제는 업솔빙 안하려고 했는데 이 문제 전까지 4개 문제를 시간내에 풀기도 했고 *1600점이라고 계속 손 놓고 있으면 평생 위상정렬과 트리 문제를 못 풀거 같아서 알고리즘을 따라하는 방식으로 업솔빙했다. 계속 하다보면 눈에 익고 알고리즘이 자동으로 튀어나올것이라고 믿고 문제풀이 시작한다.

이 문제도 well-known 위상정렬 알고리즘을 사용한 문제라고 한다. 이 문제를 풀때 사용되는 아이디어가 위상정렬을 할때 사용되는 것과 비슷하다고 한다. 먼저 일반적으로 인접 리스트로 트리를 구현하는데 여기서 추가로 배열을 하나 더 선언한다. cnt라고 선언한 이 배열은 각 노드가 가지고 있는 이웃 노드의 개수를 의미한다. 만약 두 노드로 이루어진 트리이면 각 cnt배열에는 1와 1이 저장 되어있을 것이다.

문제에서 말했듯이 이웃 노드가 1개이거나 0개일 때 리프 노드라고 말했기 때문에 처음에 cnt배열의 값이 1보다 작거나 같을 때 이 노드를 더이상 고려하지 않기 위해서 cnt배열에 INF값을 넣고 리프노드들을 queue에 넣는다.

각 리프노드에 달린 노드에 이 리프노드를 삭제하기 위해서 반복문을 $k$회 수행하는데 이때 이미 큐가 비어있으면 이 트리에는 더이상 리프노드가 없다는 뜻이므로 반복문을 break한다. 큐에 있는 리프노드 중 맨 앞을 꺼내고, 이 노드와 연결되어 있는 노드에서 리프노드를 삭제하과 cnt값을 1 줄인다. 이때 리프노드를 삭제한 노드가 이제 다시 리프노드가 되면 이 노드를 새로운 큐에 넣고 cnt배열에 INF값을 넣어서 리프노드임을 표시한다. 그리고 초기에 주어진 리프노드에 큐가 빌때까지 모든 반복을 수행하면 현재 트리에 있는 모든 리프노드를 삭제한 상태가 된다. 그리고 다른 큐에 저장한 값은 리프노드를 삭제하고 나서 새로 생긴 리프노드 값인데 이 큐를 swap 하면서 계속 갱신해준다. 이 행위를 반복하면 이 문제를 풀 수 있다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, k; cin >> n >> k;
        vector<set<int>> g(n + 1);
        vector<int> cnt(n + 1);
        for(int i = 0; i < n - 1; i++){
            int u, v; cin >> u >> v;
            cnt[u]++; 
            cnt[v]++;
            g[u].insert(v);
            g[v].insert(u);
        }

        int num = n;
        queue<int> q;
        for(int i = 1; i <= n; i++){
            if(cnt[i] <= 1){
                cnt[i] = 1e9;
                q.push(i);
            }
        }

        while(k--){
            if(q.empty()) break;
            queue<int> tmp;
            while(!q.empty()){
                int cur = q.front();
                q.pop();
                num--;
                for(auto x : g[cur]){
                    g[x].erase(cur);
                    if(--cnt[x] <= 1){
                        cnt[x] = 1e9; 
                        tmp.push(x);
                    }
                }
            }
            q.swap(tmp);
        }
        cout << num << "\n";
    }
}