BOJ 백준 4196 : 도미노

시작하면서

　이번 문제는 강한 연결 요소(SCC: Strongly Connected Component) 를 응용하는 문제이다.

BOJ 4196 - 도미노

​ SCC 개념은 해당 블로그를 추천한다. LINK

​

문제 이해

​ 이 문제는 일반적인 도미노 개념을 생각하면 된다. 최소로 도미노를 넘어뜨리기 위해서는 가장 앞, 그래프로 쉽게 말하면 위상 정렬 된 그래프에서 가장 최상위 노드를 넘어뜨리면 된다.

​ 이렇게 생각했을 때는 굳이 SCC까지 구하지 않고, Out Degree가 0 인 개수만 찾으면 될거 같지만, 사이클이 생기는 경우가 있기 때문에 해당 방법으로는 문제가 해결되지 않는다. (내가 이걸 잊고 30분이나 삽질했다)

​ 문제 해결 방법은 다음과 같다.

1. 문제에서 주어진 도미노 블록의 관계를 바탕으로 SCC를 만든다.
2. 만들어진 각 SCC 그룹끼리 Out Degree 가 있는지 확인한다.
3. Out Degree가 하나도 존재하지 않는 SCC 그룹의 개수가 문제의 답이다.

​

해결

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <math.h>

using namespace std;

class StronglyConnectedComponent
{
public:
    vector<vector<int> > graph;
    vector<vector<int> > scc;
    vector<int> dfsNumber;
    vector<int> sccNumber;
    vector<bool> finished;
    stack<int> visitedRoute;

    int currentDfsCount;
    int currentSccNumber;

    StronglyConnectedComponent(int size)
    {
        graph.resize(size + 1);
        scc.resize(size + 1);
        dfsNumber.resize(size + 1);
        sccNumber.resize(size + 1);
        finished.resize(size + 1);    

        currentDfsCount = 0;
        currentSccNumber = 0;
    }
};

int MakeStronglyConnectedComponent(StronglyConnectedComponent &scc, int currentNumber)
{
    int result = 0;

    // 1. 현재 노드의 dfs number를 대입해주고, 방문 기록 스택에 푸시한다.
    scc.dfsNumber[currentNumber] = ++scc.currentDfsCount;
    scc.visitedRoute.push(currentNumber);

    // 2. 현재 노드의 dfs number와 연결된 노드들의 dfs number 중 가장 작은 번호를 result로 사용한다.
    result = scc.dfsNumber[currentNumber];
    for (int i = 0; i < scc.graph[currentNumber].size(); i++)
    {
        int nextNumber = scc.graph[currentNumber][i];
        if (scc.dfsNumber[nextNumber] == 0)
        {
            result = min(result, MakeStronglyConnectedComponent(scc, nextNumber));
        }
        else if (scc.finished[nextNumber] == false)
        {
            result = min(result, scc.dfsNumber[nextNumber]);
        }
    }

    // 3. 현재 노드와 연결된 노드들 중 제일 높은 정점이 현재 노드일 경우, scc를 만든다.
    if (result == scc.dfsNumber[currentNumber])
    {
        vector<int> currentScc;
        while (true)
        {
            int topNumber = scc.visitedRoute.top();
            scc.visitedRoute.pop();

            currentScc.push_back(topNumber);
            scc.finished[topNumber] = true;
            scc.sccNumber[topNumber] = scc.currentSccNumber;

            if (topNumber == currentNumber)
            {
                break;
            }
        }

        // 3-1. scc를 추가한다.
        sort(currentScc.begin(), currentScc.end());
        scc.scc.push_back(currentScc);
        scc.currentSccNumber++;
    }

    return result;
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    int T, N, M;

    cin >> T;

    while (T--)
    {
        cin >> N >> M;
        
        StronglyConnectedComponent scc(N);
        for (int i = 0; i < M; i++)
        {
            int node01, node02;
            cin >> node01 >> node02;
            scc.graph[node01].push_back(node02);
        }

        // 1. SCC 만들기
        for (int i = 1; i < N + 1; i++)
        {
            if (scc.dfsNumber[i] != 0)
            {
                continue;
            }

            MakeStronglyConnectedComponent(scc, i);
        }

        // 2. 다른 SCC 그룹끼리의 간선이 있는지 체크
        vector<int> sccOutDegree(scc.currentSccNumber);
        for (int i = 1; i < N + 1; i++)
        {
            for (int j = 0; j < scc.graph[i].size(); j++)
            {
                if (scc.sccNumber[i] == scc.sccNumber[scc.graph[i][j]])
                {
                    continue;
                }

                sccOutDegree[scc.sccNumber[scc.graph[i][j]]]++;
            }
        }

        // 3. 다른 SCC에서 들어오는 간선이 없는 SCC의 개수가 답
        int result = 0;
        for (int i = 0; i < sccOutDegree.size(); i++)
        {
            if (sccOutDegree[i] == 0)
            {
                result++;
            }
        }
        
        cout << result << "\n";
    };

    return 0;
}