[백준 알고리즘] 11266번: 단절점

https://www.acmicpc.net/problem/11266

문제

문제
그래프가 주어졌을 때, 단절점을 모두 구해 출력하는 프로그램을 작성하시오.

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말한다.

입력
첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.

입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다.

출력
첫째 줄에 단절점의 개수를 출력한다.

둘째 줄에는 단절점의 번호를 공백으로 구분해 오름차순으로 출력한다.

풀이

수업에서 배우고 정리했던 단절점을 찾는 알고리즘을 그대로 적용하는 문제이다. 알고리즘은 여기 에 정리해두었다. 그래프의 각 노드들이 꼭 연결되어 있지 않아도 되기 때문에 DFS로 모든 정점을 시작점으로 두고 한번씩 탐색을 진행햐여한다. 어제 글로 알고리즘을 정리했을 때는 그렇게 어려운 부분이 없었는데, 막상 코드로 구현하려고 하니 막히는 부분들이 계속 생겼다. 한동안 고민을 하다가 구글링으로 다른 블로그들의 예시를 참고하면서 완성했다.

vector<vector<int>> adj (10001);
int back [10001];
int discover_time = 0;
bool visited[10001] = {0,};
bool result [10001] = {0,};

전역 변수는 위 처럼 다섯 개를 사용했다.

1. adj: 각 정점들의 인접 노드들을 저장하는 2차원 배열
2. discover_time: 각 정점의 탐색시간을 기록할 때 기준이 되는 타임스탬프
3. visited: 각 정점이 한번이라도 방문된 정점인지 확인하는 배열. 배열의 인덱스가 정점의 번호를 의미한다.
4. result: 해당 정점이 단절점인지 기록하는 배열 이걸 왜 사용하는지 이해가 안돼서 계속 끙끙대고 있었다..

일단 단절점을 찾으려면 각 정점들을 DFS로 탐색하면서 discover time 을 기록해두어야 한다. 이 시간을 기준으로 해서 단절점 여부를 확인할 수 있기 때문이다.

back[root] = discover_time++;

이 코드가 그 역할을 한다. 그리고 재귀적으로 DFS가 호출되면서 아래 핵심 알고리즘이 수행되는데 하나씩 살펴보자.

...
for (int i = 0 ; i < adj[root].size() ; i++){
    if (!visited[adj[root][i]]){
        child++;
        int low = dfs(adj[root][i], false);
        if (!isRoot && low >= back[root]) {
            result[root] = true;
        }
        ret = min(ret, low);
    }else{
        ret = min(ret, back[adj[root][i]]);
    }
}

if(isRoot && child >= 2){
    result[root] = true;
}
return ret;
...

한번 탐색을 진행할 따마다 자신과 연결된 모든 노드를 다 방문한다. 이때 이미 방문 했던 노드가 있다면, 다음 두 가지 경우 중 하나에 속한다.

1. 방금 가지쳐서 내려온 부모노드인 경우
2. Back Edge 가 존재하는 경우

중요한 것은 Back Edge 이지만, 어떤 경우이든간에 우리는 기준이 되는 정점과 연결된 모든 정점들의 discovery time 을 보고 가장 작은 discovery time을 선택한다. 어차피 백트랙하면서 현재 노드의 부모노드가 가진 discovery time이 업데이트 되기 때문에 1번 경우를 확인해도 로직에 문제가 생기지는 않는다.

만약 방문하지 않은 노드가 나오면 재귀호출로 해당 노드를 따라 내려간다. 재귀적으로 호출됐던 함수가 반환하면서 주는 값은 해당 노드와 연결된 모든 노드들 중 가장 작은 discovery time이 된다. 이 값을 low라는 변수에 저장해두고 백트랙했을 때 부모노드가 가진 back 값을 업데이트 해준다. 그리고 만약에 어떤 부모노드가 가진 back 값이 자녀 노드에서 리턴된 값보다 크다면, 이 부모노드의 아래에 있는 노드들은 절대 부모노드보다 앞에 있는 노드들과 연결되지 못한다. 즉, 부모노드가 단절점의 후보가 된다.

이 문제를 구현하면서 가장 의아했던 부분이 isRoot 를 사용하는 것과 child를 세어주는 것이다. 루트노드가 단절점이 되려면 2개 이상의 자녀노드를 가져야 한다는 조건이 있다는 것은 알았지만, 나는 처음에 단순하게 인접노드 리스트에 들어있는 노드의 갯수를 세어주면 된다고 생각했다. 내가 간과했던 부분은 루트노드의 인접리스트에 들어있는 노드가 루트노드가 아닌 다른 노드에 의해서 방문될 수도 있다는 것이다. 이렇게 되면 인접리스트의 갯수와는 상관없이 다른 모양의 트리가 되기 때문에 단절점이 되지 않을 수도 있게된다. 따라서 실제로 탐색이 진행될 때만 자녀노드의 갯수를 세어주는 작업이 필요하다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> adj (10001);
int back [10001];
int discover_time = 0;
bool visited[10001] = {0,};
bool result [10001] = {0,};

int dfs(int root, bool isRoot){
    visited[root] = true;
    back[root] = discover_time++;
    int ret = back[root];
    int child = 0;

    for (int i = 0 ; i < adj[root].size() ; i++){
        if (!visited[adj[root][i]]){
            child++;
            int low = dfs(adj[root][i], false);
            if (!isRoot && low >= back[root]) {
                result[root] = true;
            }
            ret = min(ret, low);
        }else{
            ret = min(ret, back[adj[root][i]]);
        }
    }
    if(isRoot && child >= 2){
        result[root] = true;
    }
    return ret;
}

int main (){
    int v, e;

    scanf("%d %d", &v, &e);

    while(e--){
        int a, b;
        scanf("%d %d", &a, &b);

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 1 ; i<= v ; i++){
        if (!visited[i]){
            dfs(i, true);
        }
    }
    int cnt = 0;
    for (int i = 1 ; i <= v ; i++){
        if (result[i]) cnt++;
    }

    printf("%d\n", cnt);
    for (int i = 1 ; i <= v ; i++){
        if (result[i])printf("%d ", i);
    }
}