백준 24461 - 그래프의 줄기

문제 링크: https://acmicpc.net/problem/24461 

24461번: 그래프의 줄기

---

문제를 요약해봅시다.

• 주어진 그래프는 사이클이 없고 간선이 $N - 1$개이므로 트리입니다.
• 가장자리 정점은 연결된 간선이 1개인 정점이고, 줄기는 가장자리 정점이 2개 이하인 그래프입니다.
• 트리의 가장자리 정점이 2개 이하가 될때까지 가장자리 정점을 지우는 것을 반복하고, 최후에 남은 정점의 목록을 출력해야 합니다.

---

이 문제는 주어진 내용을 구현하기만 하면 되는 문제입니다. 다음 과정을 반복하면 되는데요,

• 간선의 개수가 1인 정점들을 모은 후,
• 그 정점들을 모두 지우고, 연결되어 있던 정점들의 간선 수를 1개씩 줄입니다.

 

이는 위상 정렬 문제에서 볼 수 있는 기법과 비슷합니다. 답을 구현하기 위해서는 각 정점의 간선 수를 기록하는 배열과, 각 정점의 제거 여부를 기록하는 배열이 필요합니다. 위상 정렬 문제를 풀어보셨다면 쉽게 구현할 수 있습니다.

 

그러나 일반적인 위상 정렬 문제와 다르게 이 문제에서는 유의해야 할 부분이 있습니다. 매 반복마다 모든 정점이 동시에 제거된다는 것인데요.. 이는 매 반복마다 큐의 크기를 기록하고, 그 큐의 크기만큼만 반복하는 방법으로 구현하면 됩니다.

 

시간복잡도는,

• 정점의 간선 수를 기록하는데 \(O(N)\)
• \(O(N)\)개의 간선을 조사하므로 \(O(N)\)

 

총 \(O(N)\)의 시간복잡도를 갖습니다.

---

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

int main() {
    fastio;
    
    int n;
    cin >> n;
    
    vector<vector<int>> edges(n);
    vector<bool> exc(n);	// 정점의 제거 여부를 저장
    vector<int> neigh(n);	// 정점의 이웃 수를 저장
    
    // 그래프의 간선 배열을 만들고, 각 정점의 이웃 수를 계산합니다.
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        
        edges[u].push_back(v);
        edges[v].push_back(u);
        
        neigh[u]++;
        neigh[v]++;
    }
    
    // 가장자리 정점을 삽입하는 큐입니다.
    queue<int> q;
    
    // 가장자리 정점의 수를 셉니다.
    int ec = 0;
    for (int i = 0; i < n; i++) {
        if (neigh[i] == 1) {
            ec++;
        }
    }
    
    // 가장자리 정점의 수가 3개 이상이면 큐에 정점들을 삽입합니다.
    if (ec > 2) {
        for (int i = 0; i < n; i++) {
            if (neigh[i] == 1) {
                q.push(i);
                exc[i] = true;
            }
        }
    }
    
    // 그래프가 줄기만 남게 될때까지 가장자리 정점을 제거합니다.
    while (1) {
    	// 큐의 크기가 2 이하, 즉 그래프가 줄기만 남게 되면 종료합니다.
        int loop = q.size();
        if (loop <= 2) break;
        
        vector<int> next_elems;
        
        for (int i = 0; i < loop; i++) {
            int v = q.front();
            q.pop();
            
            // 큐에 담긴 정점들을 제거하고, 이웃한 정점들의 이웃 수를 1 줄입니다.
            for (int c: edges[v]) {
                if (!exc[c] && --neigh[c] == 1) {
                    next_elems.push_back(c);
                    q.push(c);
                }
            }
        }
        
        if (next_elems.size() <= 2) break;
        
        for (int x: next_elems) {
            exc[x] = true;
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (!exc[i]) cout << i << " ";
    }
}