[백준 11266] 단절점

 

 제목 그대로 단절점을 찾는 그래프 이론 문제다. 이건 정말 한참을 고민해도 떠오르지 않아서, 단절점 알고리즘을 따로 찾아 간단하게 공부하고 풀었다. 체감상 플레4 이상의 문제들은 슬슬 모르면 해법을 떠올리기 어려운 문제들이 등장하는 것 같다.

 

 일단 매번 브루트 포스로 단절점 여부를 확인하는 방법을 떠올릴 수 있으나, O(VE)의 시간 복잡도이기 때문에 문제를 해결할 순 없다. 다른 방법을 떠올려보려고 했으나, 사이클 문제 때문에 쉽사리 떠오르지가 않았다.

 

 이 문제를 해결하기 위해서는 DFS Spanning Tree를 사용해야 한다. DFS Spanning Tree는 DFS를 통해 그래프 탐색을 할 때 방문 순서를 바탕으로 형성되는 트리 구조를 일컫는다. 

 

 

 예제1을 예로 들면, 예제1을 그래프로 시각화하면 아래의 이미지 같은 형태가 될 것이다.

 

 

 이 때 임의의 노드 1번 노드를 루트로 해서, DFS를 실행하면 위의 이미지에서 나타나는 순서대로 노드를 방문하게 될 것이다(자식 노드의 숫자가 작은 걸 우선해서 방문할 경우이다, 실제 문제를 해결한 알고리즘에서는 먼저 입력된 간선을 먼저 이용한다). 그리고 그 방문 순서를 가지고 DFS Spanning Tree로 만들면 아래와 같은 형태가 된다. 초록색 숫자는 방문 순서이고, 검은색 숫자는 실제 방문 노드를 의미한다.

 

 

 그리고 나타나지 않은 인접 노드를 주황색으로 표시해 주면 위와 같다. DFS Spanning Tree를 이용하면 이런 생각을 해볼 수 있다. 어떤 노드의 자식 노드가 부모 노드를 제외한 인접 노드들을 통해 부모보다 먼저 탐색된 선조 노드에 방문할 수 있다면, 그 노드는 단절점이 아니다.

 위의 이미지에서 4번 노드(DST 상에서 2번)가 그 예시인데, 자식 노드인 5번 노드가 인접 노드를 통해 부모 노드를 거치지 않고 DST 상에서 선조 노드인 1번 노드에 방문할 수 있는 상태이다. 따라서 4번 노드는 단절점이 아니게 되고, 실제로 그래프에서 확인해 보면 4번 노드는 단절점이 아니다.

 리프 노드의 경우에는, DST 상에서 자식이 존재하지 않으므로 당연히 단절점이 아니게 된다.

 

 이 때, 예외가 발생하게 되는데 바로 판정하려는 노드가 루트 노드인 경우이다. 루트 노드는 선조 노드가 존재하지 않기 때문에, 위와 같은 판정 방식을 사용할 수 없다. 대신 루트 노드의 자식 노드가 둘 이상이라면 이는 무조건 단절점이 된다. DFS를 통해 탐색하며 만든 DST이기 때문에, 자식 노드들이 여러 개라는 것은 해당 서브 트리들이 루트 노드를 제외했을 때 서로 연결되어 있지 않음을 의미한다.

 

 예제로만 생각하다 보면 놓치기 쉬운 부분이 있는데, 단절점을 판별할 때 자식 노드의 인접 노드만 확인해서는 안된다. 자식 노드가 인접 노드를 몇 번 거쳐서 선조 노드에 도달할 수 있더라도, 탐색 중인 노드는 단절점이 아니게 된다. 그래서 DFS를 구현할 때, 리턴 값으로 인접 노드를 통해 접근 가능한 DST 인덱스가 가장 낮은 노드를 리턴하게 해 두면 좀 더 구현이 편해진다.

 

 위의 그래프 이론을 알고 나면, 구현 자체는 간단한 편이고 나는 아래와 같이 구현했다.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<vector<int> > adjList;
vector<int> dstNum;
set<int> articulationPointSet;
int dstInd = 0;

int dfs(int num) {
    dstNum[num] = ++dstInd;
    int accessibleHighestNode = dstNum[num];
    int childNum = 0;
 
    for(auto adj: adjList[num]) {
        if(dstNum[adj]>0) { // 이미 방문한 노드
            accessibleHighestNode = min(accessibleHighestNode, dstNum[adj]);
        } else {
            childNum++;
            int highestNodeByChildren = dfs(adj);
            if(dstNum[num] != 1 && highestNodeByChildren >= dstNum[num]) {
                articulationPointSet.insert(num);
            }

            accessibleHighestNode = min(accessibleHighestNode, highestNodeByChildren);
        }
    }

    if(dstNum[num] == 1 && childNum>1) articulationPointSet.insert(num); // DST root 노드, 단절점 확인
    
    return accessibleHighestNode;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int v, e;
    cin >> v >> e;

    adjList = vector<vector<int> >(v+1);
    dstNum = vector<int>(v+1, 0);

    int start, end;
    for(int i=0; i<e; i++) {
        cin >> start >> end;
        adjList[start].push_back(end);
        adjList[end].push_back(start);
    }

    for(int i=1; i<=v; i++) {
        if(dstNum[i]==0) {
            dstInd = 0;
            dfs(i);
        }
    }

    cout << articulationPointSet.size() << "\n";

    for(int point: articulationPointSet) {
        cout << point << " ";
    }
}