[Baekjoon] 11266 – 단절점

📖 문제 해석

이 문제는 무방향 그래프에서 모든 단절점을 찾아 오름차순으로 출력하는 것입니다. 예를 들어, 5개의 정점이 있는 그래프에서 정점 1이 정점 2, 3과 연결되고, 정점 2가 정점 4, 5와 연결된 상황을 생각해봅시다. 만약 정점 2를 제거한다면 {1, 3}과 {4, 5}라는 두 개의 분리된 성분이 만들어지므로, 정점 2는 단절점이 됩니다.

주목할 점은 입력 그래프가 반드시 연결 그래프가 아닐 수도 있다는 것입니다. 따라서 여러 개의 독립적인 연결 성분이 존재할 수 있으며, 각 성분에 대해 별도로 단절점을 찾아야 합니다. 또한 정점의 개수가 최대 10,000개, 간선의 개수가 최대 100,000개라는 제약 조건은 효율적인 알고리즘이 필요함을 시사합니다.

🧠 첫 번째 시도와 한계점

단절점을 찾는 가장 직관적인 방법은 각 정점을 하나씩 제거해보고 연결 성분의 개수가 증가하는지 확인하는 것입니다. 구체적으로는 각 정점 v에 대해 v와 v에 연결된 모든 간선을 임시로 제거한 후, DFS나 BFS를 통해 남은 그래프의 연결 성분 개수를 세는 방식입니다.

하지만 이 접근법은 심각한 성능 문제를 가지고 있습니다. 각 정점마다 전체 그래프를 탐색해야 하므로 시간 복잡도가 O(V × (V + E))가 됩니다. 문제에서 주어진 최대 조건인 V = 10,000, E = 100,000일 때, 이는 약 10억 번의 연산을 의미합니다. 현대 컴퓨터가 초당 10억 번 정도의 연산을 처리할 수 있다고 해도, 실제로는 상수 인수와 캐시 미스 등으로 인해 시간 초과가 발생할 가능성이 높습니다.

더욱이 이 방법은 중복된 계산을 많이 수행합니다. 각 정점을 제거할 때마다 전체 그래프를 처음부터 다시 탐색하기 때문에, 이전에 얻은 정보를 전혀 활용하지 못합니다. 분명히 더 효율적인 방법이 있을 것입니다.

💡 Tarjan의 알고리즘: 한 번의 순회로 모든 단절점 찾기

브루트포스 방법의 한계를 극복하기 위해서는 그래프의 구조적 특성을 더 깊이 이해해야 합니다. 핵심 아이디어는 DFS 트리를 구성하면서 각 정점에서 “얼마나 위로 올라갈 수 있는가”를 추적하는 것입니다.

DFS를 수행하면 자연스럽게 트리 구조가 만들어집니다. 이때 원래 그래프의 간선들은 두 종류로 분류됩니다: DFS 트리의 간선(Tree Edge)과 조상-후손 관계를 연결하는 역방향 간선(Back Edge)입니다. 무방향 그래프에서는 순방향 간선이나 교차 간선은 존재하지 않습니다.

단절점의 핵심 조건은 다음과 같습니다. 어떤 정점 u가 단절점이 되려면, u를 제거했을 때 u의 자식들이 u보다 위에 있는 정점들과 연결될 수 없어야 합니다. 즉, u의 어떤 자식 v에 대해, v와 v의 후손들이 back edge를 통해 u보다 위로 올라갈 수 없다면, u는 단절점입니다.

이를 효율적으로 판단하기 위해 두 가지 값을 각 정점에 대해 계산합니다: disc[v]는 정점 v가 DFS에서 발견된 시간을 나타내고, low[v]는 v에서 시작해서 back edge를 최대 하나 사용해서 도달할 수 있는 정점 중 가장 빠른 발견 시간을 의미합니다.

📘 Tarjan 알고리즘의 핵심 개념
Tarjan의 알고리즘은 DFS 순회 중에 disc와 low 값을 계산하여 그래프의 구조적 특성을 파악합니다. disc[v]는 정점 v의 발견 시간이고, low[v]는 v에서 back edge를 통해 도달할 수 있는 가장 이른 조상의 발견 시간입니다. 이 두 값의 관계를 통해 단절점, 다리, 강연결성분 등을 O(V + E) 시간에 찾을 수 있습니다.

루트가 아닌 정점 u가 단절점이 되는 조건은 u의 어떤 자식 v에 대해 low[v] >= disc[u]인 경우입니다. 이는 v와 v의 서브트리가 back edge를 통해 u보다 위로 올라갈 수 없음을 의미하므로, u를 제거하면 v의 서브트리가 분리됩니다.

루트 정점의 경우는 특별히 처리해야 합니다. 루트는 부모가 없으므로 위의 조건을 적용할 수 없습니다. 대신 루트가 둘 이상의 자식을 가질 때만 단절점이 됩니다. 루트를 제거했을 때 각 자식의 서브트리들이 서로 분리되기 때문입니다.

🔍 알고리즘 동작 과정 시뮬레이션

구체적인 예제를 통해 알고리즘의 동작을 따라가 보겠습니다. 다음과 같은 그래프를 고려해봅시다:

정점: 1, 2, 3, 4, 5, 6
간선: (1,2), (1,3), (2,4), (3,4), (4,5), (5,6)

정점 1에서 DFS를 시작한다고 가정합시다.

Step 1: 정점 1 방문 (timer = 1)

  • disc[1] = low[1] = 1
  • 정점 2로 이동

Step 2: 정점 2 방문 (timer = 2)

  • disc[2] = low[2] = 2
  • 정점 4로 이동

Step 3: 정점 4 방문 (timer = 3)

  • disc[4] = low[4] = 3
  • 정점 3으로 이동 (미방문)

Step 4: 정점 3 방문 (timer = 4)

  • disc[3] = low[3] = 4
  • 정점 1 확인 (이미 방문, back edge 발견)
  • low[3] = min(4, 1) = 1
  • 정점 4로 돌아가면서 low[4] = min(3, 1) = 1

Step 5: 정점 4에서 정점 5로 이동 (timer = 5)

  • disc[5] = low[5] = 5
  • 정점 6으로 이동

Step 6: 정점 6 방문 (timer = 6)

  • disc[6] = low[6] = 6
  • 정점 5로 돌아가면서, low[5]는 여전히 5
  • low[5] >= disc[4] (5 >= 3)이므로 정점 4는 단절점

최종적으로 정점 4가 단절점으로 식별됩니다. 실제로 정점 4를 제거하면 {1, 2, 3}과 {5, 6}으로 그래프가 분리됩니다.

💻 소스 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 10000

int V, E, A, B;
bool ans[MAX_N+1];          <em>// 각 정점이 단절점인지 저장</em>
bool vis[MAX_N+1];          <em>// DFS 방문 체크 배열</em>
int disc[MAX_N+1], low[MAX_N+1];  <em>// 발견 시간과 low 값 저장</em>
int timer = 0;              <em>// DFS 진행 중 시간 카운터</em>
unordered_map<int, vector<int>> G;  <em>// 인접 리스트로 그래프 표현</em>

void dfs(int node, int parent) {
    <em>// 현재 노드의 발견 시간과 low 값을 현재 타이머로 초기화</em>
    disc[node] = low[node] = ++timer;
    vis[node] = true;  <em>// 방문 표시</em>
    
    int child = 0;  <em>// 루트 노드의 자식 개수 카운트용</em>
    
    <em>// 현재 노드의 모든 인접 노드를 확인</em>
    for (auto & x: G[node]) {
        if (!vis[x]) {  <em>// 아직 방문하지 않은 노드인 경우</em>
            if (x != parent) child++;  <em>// 루트가 아닌 경우 자식 수 증가</em>
            
            dfs(x, node);  <em>// 재귀적으로 자식 노드 탐색</em>
            
            <em>// 자식의 low 값이 현재 노드의 disc 값보다 크거나 같으면</em>
            <em>// 현재 노드를 제거했을 때 자식 서브트리가 분리됨</em>
            if (low[x] >= disc[node]) {
                ans[node] = true;  <em>// 단절점으로 표시</em>
            }
            
            <em>// 현재 노드의 low 값을 자식의 low 값으로 업데이트</em>
            low[node] = min(low[node], low[x]);
            
        } else if (x != parent) {  <em>// 이미 방문한 노드이지만 부모가 아닌 경우 (back edge)</em>
            <em>// back edge를 통해 도달 가능한 조상 중 가장 이른 발견 시간으로 업데이트</em>
            low[node] = min(low[node], disc[x]);
        }
    }
    
    <em>// 루트 노드의 특별한 처리: 2개 이상의 자식을 가져야 단절점</em>
    if (parent == -1) {
        ans[node] = child >= 2;
    }
}

int main()
{
    ios::sync_with_stdio(false);  <em>// 입출력 성능 향상</em>
    cin.tie(nullptr);
    
    memset(ans, false, sizeof(ans));  <em>// 단절점 배열 초기화</em>
    cin >> V >> E;
    
    <em>// 그래프 구성: 무방향 그래프이므로 양쪽에 간선 추가</em>
    for (int i = 0; i < E; ++i) {
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    
    <em>// 모든 정점에 대해 DFS 수행 (연결되지 않은 성분들 처리)</em>
    for (int i = 1; i <= V; ++i) {
        if (vis[i]) continue;  <em>// 이미 방문한 성분은 스킵</em>
        dfs(i, -1);  <em>// 각 연결 성분의 루트에서 DFS 시작</em>
    }
    
    <em>// 단절점들을 벡터에 수집하여 정렬된 출력 준비</em>
    vector<int> cut;
    for (int i = 1; i <= V; ++i) {
        if (ans[i]) cut.push_back(i);
    }
    
    <em>// 결과 출력: 단절점 개수와 단절점들의 번호</em>
    cout << cut.size() << "\n";
    for (auto &x : cut) {
        cout << x << " ";
    }
    
    return 0;
}

🔁 대안적 접근법

앞서 언급한 브루트포스 방법 외에도, Union-Find 자료구조를 활용한 방법을 고려할 수 있습니다. 각 정점을 하나씩 제거하면서 Union-Find를 사용해 연결 성분의 개수를 추적하는 방식입니다. 하지만 이 방법도 여전히 O(V × E × α(V)) 정도의 시간이 걸리므로 Tarjan의 알고리즘보다 비효율적입니다.

또 다른 접근법으로는 네트워크 플로우를 이용한 방법이 있습니다. 각 정점을 두 개로 분할하고 용량 1인 간선으로 연결한 후, 정점 분할로 인해 최대 플로우가 감소하는 정점을 찾는 방식입니다. 하지만 이는 구현이 복잡하고 시간 복잡도도 더 높습니다.

📌 핵심 통찰과 정리

단절점 찾기 문제의 핵심은 DFS 트리 구조를 활용하여 그래프의 연결성을 효율적으로 분석하는 것이었습니다. Tarjan의 알고리즘은 단 한 번의 DFS 순회로 모든 단절점을 찾아내는 우아한 해결책을 제시합니다.

이 문제를 통해 우리는 low 값이라는 개념을 이해하게 되었습니다. 이는 각 정점에서 back edge를 통해 도달할 수 있는 가장 이른 조상을 나타내며, 이 정보를 통해 어떤 정점을 제거했을 때 그래프가 분리되는지 판단할 수 있습니다. 또한 루트 노드의 특별한 경우를 처리하는 방법도 배웠습니다.

이러한 아이디어는 단절점뿐만 아니라 다리(bridge) 찾기, 강연결성분 분해 등 다양한 그래프 문제에 응용될 수 있는 강력한 도구입니다.

Similar Posts