[백준 알고리즘] 2150번: Strongly Connected Component

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

문제

문제
방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.

방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.

![](https://www.acmicpc.net/JudgeOnline/upload/201008/scco.PNG” />

예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다.

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

출력
첫째 줄에 SCC의 개수 K를 출력한다. 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.

풀이

알고리즘만 봤을 때는 단순해보였는데, 실제로 풀어보니 쉽지 않았고 꽤 많은 시간이 걸렸다. 알고리즘은 정말 단순하다. 주어진 그래프를 DFS로 순회해서 각 노드마다 탐색이 완전히 끝나는 Finish Time을 기록하고, 그래프의 각 간선을 역방향으로 만든 뒤에, Finish Time 이 컸던 순서대로 각 노드를 시작점으로 삼아 트리를 만들면 된다.

문제에서 생각보다 고려해야할 요소가 있었으니 하나씩 다시 정리해보자.

Transposed Graph

그래프에 역방향을 취하는 것은 간단했다. 처음에 입력을 받으면서 별도의 역방향 그래프를 저장하는 Adjacency List 를 만들어두고 그곳에도 함께 저장을 해주었다.

Finish Time

수업시간에 배웠던 Finish Time을 기록하는 방법은 최초에 count와 같은 0에서부터 시작하는 카운터 변수를 만들고 각 노드의 탐색이 시작될 때와 끝날 때 카운터를 하나씩 올리면서 탐색의 시작시간과 끝시간을 기록하는 것이었다. 그런데 이 문제에서는 기존 그래프에 대해 DFS를 마쳤을 때, Finish Time 을 기준으로 정렬을 해주어야 하는데, 정렬과정에서 각 Finish Time에 대한 정점을 인덱스로 관리했기 때문에 정렬이후에는 위치가 어디였는지 파악하는 것이 어려웠다.

Pair 를 사용해볼까 했지만 너무 코드가 더러워졌고, 구글링을 통해서 스택을 사용하는 힌트를 얻었다. 사실 위상정렬을 구현할 때 스택을 사용했던 것을 기억했다면 쉬웠을텐데 역시 문제를 풀긴 풀긴 풀어도 확실히 내 것이 되는데는 훈련이 필요한 것 같다. 스택을 통해서 구현하기 위해서 dfs 함수가 리턴되는 것이 해당 노드에 대한 탐색이 끝났다는 의미이기 때문에 dfs 함수 제일 끝에 스택에 노드 번호를 저장해주었다.

Count & Sorting

일단 SCC가 몇개인지 출력을 마지막에 해주어야 하는데, 출력 위치가 가장 처음이다. 이 말은 그냥 역방향 그래프를 순회하면서 Path를 출력해주면 안된다는 것을 의미한다. 결과를 따로 어딘가에 저장해야하기 때문에 나는 result 라는 vector<vector<int>> 타입의 변수를 만들어서 한 정점에 대한 탐색결과를 저장해주었다. 벡터의 크기를 너무 크게 만들어놓으면 안될 것 같아 탐색이 가능한 각 정점을 벡터에 하나씩 넣어주는 방법으로 저장했다.

정렬은 2차원 벡터이기 때문에 각 행에 해당하는 벡터를 먼저 정렬해주고 정렬이 완료된 벡터들을 첫 열을 기준으로 다시 정렬해주었다.

Memory Space

이 문제를 풀면서 제일 힘들었던 부분이 메모리 관리에 대한 부분이었다. 테스트케이스를 통과해서 기쁘게 문제를 제출했는데 메모리초과로 오답처리가 되었다. 나는 코드를 단순화 시키려고 SCC와 초기 탐색을 위한 DFS를 한 함수로 공유하게끔 했었는데, 파라미터로 Adjacency List를 넘겨주었다. 내가 아주 잘못 생각했던 부분이다. 함수가 재귀적으로 계속 호출되면서, 길이 최대 10001 X 10001 에 해당하는 2차원 벡터가 계속해서 새로 생성된 것이다. 아주 기초적인 부분이었는데 놓친게 아쉬웠다. 결국 두 개의 함수로 기능을 나누고, 벡터를 전역변수로 선언해서 사용해서 해결했다.

코드

#include <cstdio>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

bool visited[10001];
vector<vector<int>> result;
vector<vector<int>> adj;
vector<vector<int>> adjTrans;

stack<int>stk;

void dfs(int root){
    visited[root] = true;
    for (int  i = 0 ; i < adj[root].size() ; i++){
        if (!visited[adj[root][i]]){
            dfs(adj[root][i]);
        }
    }
    stk.push(root);
}

void scc(int root){
    visited[root] = true;
    for (int  i = 0 ; i < adjTrans[root].size() ; i++){
        if (!visited[adjTrans[root][i]]){
            scc(adjTrans[root][i]);
            result.back().push_back(adjTrans[root][i]);
        }
    }
}

int main (){
    int V, E;

    scanf("%d %d", &V, &E);

    adj.resize(V+1);
    adjTrans.resize(V+1);

    for (int i = 0 ; i < E  ; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adjTrans[b].push_back(a);
    }

    for (int i = 1 ; i <= V ; i++){
        if(!visited[i]){
            dfs(i);
        }
    }

    for (int i = 0 ; i <=V ; i++) visited[i] = false;

    while(!stk.empty()){
        if (!visited[stk.top()]){
            vector<int> temp(1);
            temp[0] = stk.top();
            result.push_back(temp);
            scc(stk.top());
        }
        stk.pop();
    }

    printf("%lu\n", result.size());

    for (int i = 0 ; i < result.size() ; i++){
        sort(result[i].begin(), result[i].end());
    }

    sort(result.begin(), result.end());
    for (auto v : result){
        for (auto i : v){
            printf("%d ", i);
        }
        printf("-1\n");
    }
}