[백준 4196] 도미노 C++

4196번: 도미노

강한 연결 요소

---

1.  문제 해결 아이디어

 

강한 연결 요소 (SCC) - 타잔 알고리즘

타잔 알고리즘을 사용해서 풀었다.

개인적으로 코사라주보다 직관적이고 이해하기 편해서 SCC문제를 풀 때는 주로 타잔 알고리즘을 사용할 것 같다.

 

 

하나의 도미노가 무너지면 다른 도미노에 영향을 끼친다.

임의의 도미노에서 출발해서, 이어질 수 있는 모든 도미노는 무너질 것이다!

 

특정 도미노들이 사이클을 이룬다고 하면 사이클을 이루는 도미노들 중에서 하나만 넘어져도 사이클에 속한 모든 도미노는 무너질 것이다!

이 사실로 보아 SCC문제라고 생각할 수 있다.

 

하지만 도미노의 답은 단순한 SCC는 아니다.

 

1 -> 2

2 -> 3

3 -> 1

4 -> 3

5 -> 4

위와 같은 연결이 형성되어있을 때 SCC는 (1,2,3), (4), (5) 이렇게 3개이지만

5번 도미노를 처음에 무너뜨리면 모든 도미노를 무너뜨릴 수 있어서 한 번의 터치가 답이된다.

 

그러면 답을 어떻게 구하냐

 

각 정점은 사이클에 속하든 속하지 않든 dfs방문 순서와 SCC생성 순서에 따라서 반드시 어떤 SCC에 속하게 된다.

 

위 예시에서 (1,2,3)을 1번 SCC, (4)를 2번 SCC, (5)를 3번 SCC라고 하자.

SCC간의 연결을 고려했을 때 SCC(3) -> SCC(2) -> SCC(1) 이렇게 연결되어있다.

 

처음에 5번 도미노를 무너뜨리면 모든 도미노를 무너뜨릴 수 있었다.

5번 도미노는 3번 SCC이다.

3번 SCC의 특징! => SCC의 indegree가 0이다!

 

곰곰히 생각해보자

어떤 도미노가 SCC를 건드리면 SCC내부는 모두 무너질 것이고 하나의 도미노로 취급해도 될 것이다.

그럼 건드릴 수 없는(indegree가 0인)SCC는 어떻게 무너질까?

 - 손으로 넘어뜨려야지

그래서 indegree가 0인 SCC의 개수가 답이될것이다.!

 

그럼 SCC의 indegree를 각각 구하면 되겠다

 

모든 정점의 연결을 살펴보면서 두 정점의 SCC가 같다면 연결을 당하는? SCC의 indegree를 1 증가시켜준다.

 

그리고 모든 SCC의 indegree를 검사하면서 indegree값이 0인 SCC의 개수를 출력하면 끝이다.

---

2.  코드

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int N, M;
vector< vector<int> > adj;
vector<int> stk;
 
int sccindegree[100001];
int SCCID[100001];
int Vertexcnt, SCCcnt;
int discovered[100001];
 
int SCC(int now){
    int ret = discovered[now] = Vertexcnt++;
    
    stk.push_back(now);
    
    for(auto &next : adj[now]){
        if(discovered[next] == -1){
            ret = min(ret, SCC(next));
        }
        else if(SCCID[next] == -1){
            ret = min(ret, discovered[next]);
        }
    }
    
    if(ret == discovered[now]){
        while(1){
            int temp = stk.back();
            stk.pop_back();
            SCCID[temp] = SCCcnt;
            if(temp == now) break;
        }
        SCCcnt++;
    }
    
    return ret;
}
 
void init(){
    memset(discovered, -1, sizeof(discovered));
    memset(SCCID, -1, sizeof(SCCID));
    memset(sccindegree, 0, sizeof(sccindegree));
    adj.clear();
    adj.resize(N+1, vector<int>());
    Vertexcnt = SCCcnt = 0;
    
    int u, v;
    for(int i = 0; i < M; i++){
        cin >> u >> v;
        adj[u].push_back(v);
    }
}
 
void solve(){
    int result = 0;
    
    for(int i = 1; i <= N; i++){
        if(discovered[i] != -1) continue;
        SCC(i);
    }
    
    for(int i = 1; i <= N; i++){
        for(auto &w : adj[i]){
            if(SCCID[w] == SCCID[i]) continue;
            sccindegree[SCCID[w]]++;
        }
    }
    
    for(int i = 0; i < SCCcnt; i++){
        if(!sccindegree[i]) result++;
    }
    
    cout << result << "\n";
}
 
int main(){
    // cout.tie(0)를 넣어주면 런타임에러가 발생한다 왜?? 
    ios::sync_with_stdio(0), cin.tie(0);
    int test;
    cin >> test;
    while(test--){
        cin >> N >> M;
        
        init();
        solve();
        
    }
    
    return 0;
}

 

의식의 흐름대로 풀이를 써봤다

개인적으로 이게 더 편하다

글을 쓸 때 압축해서 간결하게 쓰고싶은 마음이 컸는데 피곤해서 대충..쓰는 느낌으로 쓰니까 더 편하고 잘 써지는것 같다

 

 

 

글쓰는 스타일, 문제 풀이 해석 등에 대한 피드백 감사히 받겠습니다.