[Baekjoon] 11400 – 단절선

📖 문제 이해하기

단절선 문제는 주어진 그래프에서 “제거했을 때 연결 요소의 개수가 증가하는 간선”을 모두 찾는 문제입니다. 쉽게 말해, 어떤 다리를 끊었을 때 원래 하나였던 섬이 두 개로 분리되는 그 다리를 찾는 것입니다.

예를 들어, 정점 5개와 간선 5개로 구성된 그래프가 있다고 해봅시다: 1-2, 2-3, 3-4, 3-5, 4-5. 여기서 간선 1-2나 2-3을 제거하면 그래프가 두 개의 분리된 부분으로 나누어집니다. 반면 3-4나 4-5를 제거해도 모든 정점은 여전히 연결된 상태를 유지합니다.

문제의 핵심 제약사항은 정점 수가 최대 100,000개, 간선 수가 최대 1,000,000개라는 점입니다. 이는 효율적인 알고리즘이 필수임을 의미합니다.

🧠 첫 번째 시도와 한계점

단절선을 찾는 가장 직관적인 방법은 각 간선을 하나씩 제거해보고, 그래프의 연결성이 변하는지 확인하는 것입니다. 구체적으로는 간선 하나를 제거한 후 DFS나 BFS로 전체 그래프를 탐색하여 모든 정점에 도달 가능한지 검사하는 방식입니다.

이 접근법은 개념적으로는 완전히 정확하지만, 시간 복잡도 측면에서 치명적인 문제가 있습니다. 간선이 E개 있을 때 각각에 대해 O(V + E) 시간의 그래프 탐색을 수행해야 하므로, 전체 시간 복잡도는 O(E × (V + E))가 됩니다.

최악의 경우를 생각해보면, V = 100,000, E = 1,000,000일 때 약 10^12번의 연산이 필요합니다. 이는 현실적으로 수 분에서 수 십분의 실행 시간을 의미하며, 대부분의 온라인 저지 시스템에서 시간 초과를 받게 됩니다.

더 근본적인 문제는 이 방법이 각 간선을 독립적으로 처리한다는 점입니다. 그래프 탐색 과정에서 얻는 구조적 정보를 전혀 활용하지 못하고, 매번 처음부터 다시 시작해야 합니다.

💡 Tarjan 알고리즘: 한 번의 탐색으로 모든 단절선 찾기

단단절선을 효율적으로 찾는 핵심 아이디어는 DFS 트리의 구조적 특성을 활용하는 것입니다. 1972년 로버트 타잔이 제안한 이 알고리즘은 단 한 번의 DFS 탐색으로 모든 단절선을 찾아냅니다.

핵심 통찰력은 다음과 같습니다: 어떤 간선이 단절선이 되려면, 그 간선을 통하지 않고는 그래프의 한 부분에서 다른 부분으로 갈 수 없어야 합니다. DFS 트리에서 이는 “자식 서브트리에서 조상으로 돌아가는 우회 경로가 존재하지 않는 경우”와 정확히 일치합니다.

이를 판단하기 위해 각 정점에 대해 두 가지 값을 추적합니다. dfs_num[v]는 정점 v를 방문한 순서(DFS 번호)이고, dfs_low[v]는 정점 v에서 시작하여 하나의 역방향 간선(back edge)을 최대 한 번 사용해서 도달할 수 있는 정점 중 가장 작은 DFS 번호입니다.

간선 (u, v)가 단절선이 되는 조건은 dfs_low[v] > dfs_num[u]입니다. 이는 v의 서브트리에서 u보다 앞서 방문된 정점에 도달할 수 없다는 의미이며, 곧 (u, v) 간선이 유일한 연결 통로라는 것을 나타냅니다.

반대로, dfs_low[v] == dfs_num[u]인 경우는 매우 특별한 의미를 가집니다. 이는 자식 v의 서브트리에서 정확히 부모 u까지는 도달할 수 있지만, 그보다 더 위의 조상에는 도달할 수 없다는 뜻입니다. 하지만 이 경우에도 (u, v) 간선은 단절선이 아닙니다. 왜냐하면 v의 서브트리가 u에 도달할 수 있다는 것 자체가 (u, v) 간선 외의 다른 경로가 존재함을 의미하기 때문입니다.

더 구체적으로 설명하면, dfs_low[v] == dfs_num[u]라는 것은 v의 서브트리 내의 어떤 정점에서 역방향 간선을 통해 u에 직접 연결되는 경로가 존재한다는 뜻입니다. 따라서 (u, v) 간선을 제거하더라도 v의 서브트리와 나머지 그래프는 여전히 연결될 수 있습니다. 즉, (u, v) 간선을 없앤다고 해도, v를 통해서 갈 수 있는 가장 높은 곳이 u이므로, 둘은 반드시 연결되어 있습니다.

📘 Tarjan 알고리즘에 대하여
1972년 로버트 타잔이 개발한 이 알고리즘은 그래프의 강연결성분, 단절점, 단절선을 효율적으로 찾는 범용적인 기법입니다. DFS 트리의 구조와 역방향 간선의 정보를 조합하여 O(V + E) 시간에 복잡한 그래프 구조 문제를 해결합니다. 네트워크 분석, 회로 설계, 컴파일러 최적화 등 다양한 분야에서 활용되고 있습니다.

알고리즘의 작동 방식을 더 자세히 살펴보면, DFS 탐색 중에 각 정점에서 dfs_low 값을 계산하는 과정이 핵심입니다. 정점 u에서 인접한 정점 v를 방문할 때, v가 아직 방문되지 않았다면 재귀적으로 dfs(v, u)를 호출한 후, dfs_low[u]를 min(dfs_low[u], dfs_low[v])로 업데이트합니다. 만약 v가 이미 방문되었고 u의 부모가 아니라면, dfs_low[u]를 min(dfs_low[u], dfs_num[v])로 업데이트합니다.

이러한 업데이트 규칙이 dfs_low 값의 정확성을 보장하며, 동시에 단절선 판정 조건인 dfs_low[v] > dfs_num[u]를 올바르게 검사할 수 있게 해줍니다.

🔍 알고리즘 동작 과정 살펴보기

구체적인 예제를 통해 알고리즘이 어떻게 작동하는지 살펴보겠습니다. 다음과 같은 그래프가 있다고 가정합시다:

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

정점 1에서 시작하여 DFS를 수행합니다.

  1. 정점 1 방문 (dfs_num[1] = 1, dfs_low[1] = 1)
    • 인접한 정점 2로 이동
  2. 정점 2 방문 (dfs_num[2] = 2, dfs_low[2] = 2)
    • 인접한 정점 4로 이동
  3. 정점 4 방문 (dfs_num[4] = 3, dfs_low[4] = 3)
    • 인접한 정점 6으로 이동
  4. 정점 6 방문 (dfs_num[6] = 4, dfs_low[6] = 4)
    • 인접한 정점 5로 이동
  5. 정점 5 방문 (dfs_num[5] = 5, dfs_low[5] = 5)
    • 인접한 정점 3으로 이동 (아직 미방문)
  6. 정점 3 방문 (dfs_num[3] = 6, dfs_low[3] = 6)
    • 인접한 정점 1은 이미 방문됨 (부모가 아님)
    • dfs_low[3] = min(6, 1) = 1로 업데이트
  7. 정점 3에서 복귀: dfs_low[5] = min(5, 1) = 1로 업데이트
  8. 정점 5에서 복귀: dfs_low[6] = min(4, 1) = 1로 업데이트
  9. 정점 6에서 복귀: dfs_low[4] = min(3, 1) = 1로 업데이트
  10. 정점 4에서 복귀: dfs_low[2] = min(2, 1) = 1로 업데이트

이제 단절선 판정을 수행합니다.

  • 간선 (1,2): dfs_low[2] = 1, dfs_num[1] = 1 → 1 > 1은 거짓
  • 간선 (2,4): dfs_low[4] = 1, dfs_num[2] = 2 → 1 > 2는 거짓
  • 나머지 간선들도 모두 거짓

이 예제에서는 모든 정점이 여러 경로로 연결되어 있어 단절선이 존재하지 않습니다.

💻 구현 코드

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

#define MAX_N 100000

int V, E, A, B;
vector<pair<int,int>> ans;  <em>// 단절선들을 저장할 벡터</em>
int dfs_num[MAX_N+1], dfs_low[MAX_N+1];  <em>// DFS 번호와 low 값 배열</em>
bool vis[MAX_N+1];  <em>// 방문 여부를 체크하는 배열</em>
int dfs_number = 0;  <em>// DFS 번호를 할당하기 위한 전역 카운터</em>
vector<int> G[MAX_N+1];  <em>// 인접 리스트로 그래프를 표현</em>

void dfs(int node, int parent) {
    <em>// 현재 노드에 DFS 번호를 할당하고, 초기값으로 low 값도 동일하게 설정</em>
    dfs_num[node] = dfs_low[node] = ++dfs_number;
    vis[node] = true;  <em>// 현재 노드를 방문했다고 표시</em>
    
    <em>// 현재 노드와 인접한 모든 노드를 탐색</em>
    for (auto &x : G[node]) {
        if (!vis[x]) {  <em>// 아직 방문하지 않은 노드라면</em>
            dfs(x, node);  <em>// 재귀적으로 DFS 수행 (x가 자식, node가 부모)</em>
            
            <em>// 자식 노드에서 돌아온 후, 단절선 조건 검사</em>
            if (dfs_low[x] > dfs_num[node]) {
                <em>// x의 서브트리에서 node보다 앞서 방문된 노드로 갈 수 없다면</em>
                <em>// (node, x) 간선은 단절선임</em>
                ans.push_back({min(node, x), max(x, node)});
            }
            
            <em>// 자식의 low 값으로 현재 노드의 low 값 업데이트</em>
            dfs_low[node] = min(dfs_low[node], dfs_low[x]);
            
        } else if (x != parent) {  <em>// 이미 방문된 노드이고 부모가 아니라면</em>
            <em>// 역방향 간선을 발견한 경우, x의 DFS 번호로 low 값 업데이트</em>
            dfs_low[node] = min(dfs_low[node], dfs_num[x]);
        }
        <em>// x가 parent인 경우는 무시 (부모로 돌아가는 간선은 역방향 간선이 아님)</em>
    }
}

int main() {
    ios::sync_with_stdio(false);  <em>// 입출력 속도 최적화</em>
    cin.tie(nullptr);
    
    memset(vis, false, sizeof(vis));  <em>// 방문 배열을 false로 초기화</em>
    
    cin >> V >> E;  <em>// 정점 개수와 간선 개수 입력</em>
    
    <em>// E개의 간선 정보를 입력받아 인접 리스트 구성</em>
    for (int i = 0; i < E; ++i) {
        cin >> A >> B;
        G[A].push_back(B);  <em>// A에서 B로 가는 간선 추가</em>
        G[B].push_back(A);  <em>// B에서 A로 가는 간선 추가 (무방향 그래프)</em>
    }
    
    <em>// 정점 1에서 시작하여 DFS 수행 (문제에서 그래프가 연결되어 있다고 보장)</em>
    dfs(1, -1);  <em>// 부모는 -1 (존재하지 않음)</em>
    
    cout << ans.size() << "\n";  <em>// 찾은 단절선의 개수 출력</em>
    
    <em>// 단절선들을 사전순으로 정렬하여 출력</em>
    sort(ans.begin(), ans.end());
    for (auto &x : ans) {
        cout << x.first << " " << x.second << "\n";
    }
    
    return 0;
}

🔁 대안적 접근법

단절선 문제를 해결하는 다른 방법으로는 유니온-파인드(Union-Find) 자료구조를 활용한 접근법이 있습니다. 이 방법은 각 간선을 하나씩 추가하면서 연결 요소의 변화를 관찰하는 방식으로 작동합니다.

구체적으로는 처음에 모든 정점을 분리된 상태로 두고, 간선을 하나씩 추가하면서 어떤 간선이 두 개의 서로 다른 연결 요소를 처음으로 연결하는지 확인합니다. 하지만 이 방법은 단절선의 정의와 정확히 반대 방향으로 접근하기 때문에, 추가적인 논리적 변환이 필요하고 구현이 복잡해집니다.

또 다른 방법으로는 강연결성분(Strongly Connected Components) 알고리즘을 변형하여 사용하는 것입니다. 하지만 우리가 다루는 것은 무방향 그래프이므로, 이 접근법은 과도하게 복잡합니다.

결국 Tarjan의 단절선 알고리즘이 가장 직접적이고 효율적인 해법입니다.

📌 핵심 요약 및 배운 점

단절선 문제는 처음에는 “간선을 하나씩 제거해보자”라는 직관적인 접근을 유도하지만, 이는 시간 복잡도 측면에서 실용적이지 않습니다. Tarjan 알고리즘의 핵심은 DFS 트리의 구조적 정보를 활용하여 단 한 번의 탐색으로 모든 단절선을 찾는 것입니다.

이 알고리즘을 통해 우리는 그래프에서 “구조적 취약점”을 효율적으로 식별할 수 있습니다. 네트워크 설계, 도로 교통 시스템 분석, 소셜 네트워크 연구 등 실제 응용 분야에서 매우 유용한 도구입니다.

가장 중요한 통찰력은 dfs_low[v] > dfs_num[u] 조건이 간선 (u, v)의 단절선 여부를 정확히 판정한다는 점입니다. 이는 DFS 트리에서 자식 서브트리가 조상으로 돌아갈 우회 경로가 없음을 의미하며, 곧 해당 간선이 연결성의 병목점임을 나타냅니다.

Similar Posts