백준 4196 도미노

www.acmicpc.net/problem/4196

4196번: 도미노

본 블로그 SCC관련 포스팅에서 num값이 크면 가장 멀리 있는 정점까지 도달할 수 있는 가능성이 있다고 하였다. 약간 위상정렬에서 순서가 가장 앞서는 정점에서 시작해야 모든 정점을 돌 수 있는 것처럼, SCC를 찾을 때 첫 번째 DFS에서 매겨둔 num값 중 가장 큰 값에서 시작하면 가장 멀리 갈 가능성이 있다. (절대 항상 그런건 아니다. 주의!)

이 도미노 문제는 어떠한 블록을 넘어뜨리면 가장 멀리 가는 경우 (또는 가장 많은 개수)를 찾는 게 아니다. 최소 몇 개만으로 모든 블록을 넘어뜨릴 수 있는지 찾는 것이기에, 위에서 언급했던 것처럼, 가장 큰 num값부터 체크해나가면 된다. 

필자는 이 문제를 결국 SCC를 찾는 방법 중의 하나인 코사라주 알고리즘에서 첫 번째 DFS만을 사용했고, 이후 BFS를 통해 답을 구하였다.

 

이 문제를 단순 DFS로 '트리 갯수 구하기'나 위상정렬로 풀 순 없을까?라는 생각도 해보았다.

일단 단순 DFS로는 힘들다. 왜냐하면 이 문제에서 그래프는 방향 그래프이기 때문이다. 어느 점에서 시작해야 하는지 알 수 없다. 

1->2->3->4로 연결된 방향그래프가 있다면, 1을 넘어뜨리면 모두 넘어지지만, 2에서 시작하면 1이 남는다...

 

위상정렬로도 힘들다. 왜냐하면 그래프상에 사이클이 있기 때문이다. 위상정렬로 순서를 정해줄 때, 사이클에 포함된 점들은 순서에 포함되지 않는다. 사이클이 있는지 없는지 검사는 할 수 있지만, 사이클을 이루는 점들에 대한 순서를 정해주기 힘들다.

 

따라서 SCC를 이용한 풀이가 적합하다.

그리고 이 문제는 가장 멀리 갈 가능성이 있는 점들부터 나열해주는 과정만 있으면 되므로, 코사라주 알고리즘의 2번째 DFS도 필요 없고, 역방향 그래프도 필요 없다.

위와 같이, 각 정점에 대한 num값을 매겨두고, 높은 값을 가진 정점에서부터 블록을 넘어뜨려가면 된다. 위의 예시에서는 1번 블록을 넘어뜨리면(2와 3도 가능) 모든 블록을 넘어뜨릴 수 있다. (이는 BFS로 방문체크하여 관리한다.)

 

<주요 내용>

코사라주 알고리즘, DFS, BFS, 스택

 

<코드>

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#define endl '\n'
using namespace std;
int t,n,m,a,b,cnt,num;
const int sz=1e5+1;
queue<int>q;
stack<int>st;
vector<int>graph[sz];
bool visited[sz];

void scc(int node){
    if(!visited[node]){
        visited[node]=1;
        for(int nx:graph[node])scc(nx);
        st.push(node);
        num++;
    }
}
void bfs(int start){
    visited[start]=1;
    q.push(start);
    while(!q.empty()){
        int curr=q.front();q.pop();
        for(int nx:graph[curr]){
            if(!visited[nx]){
                visited[nx]=1;
                q.push(nx);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>t;
    while(t--){
        cin>>n>>m;
        num=0;cnt=0;
        for(int i=1;i<=n;++i){
            graph[i].clear();
        }
        fill(visited+1,visited+n+1,0);
        while(m--){
            cin>>a>>b;
            graph[a].push_back(b);
        }
        for(int i=1;i<=n;++i)scc(i);
        fill(visited+1,visited+n+1,0);
        while(!st.empty()){
            int curr=st.top();st.pop();
            if(!visited[curr]){
                cnt++;
                bfs(curr);
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}