[C++] 4196번 도미노 - 그래프 이론, 강한 연결 요소

1. 문제

• 한 도미노 블록이 넘어지면 다음 도미노가 연쇄적으로 쓰러진다. 그러나 특정 다른 블록을 넘어뜨리지 못하게 배치되어 있다면 수동으로 넘어뜨려야 한다.
• 각 도미노 블록 배치가 주어질 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하라.

<입력>

• - 1 -   테스트케이스의 개수 T
  • - 1 -   정수 \(N, M(1 \leq N \leq 100,000)\)
    • N: 도미노 개수, M: 관계의 개수
    • 도미노 블록 번호는 1~N사이 정수다.
  • - M개의 줄 -   두 정수 x, y(x번 블록이 넘어지면 y번 블록도 넘어짐)

<출력>

• 손으로 넘어뜨리는 최소의 도미노 블록 개수 출력

2. 재정의

• 모든 노드를 다 지나기 위해 시작해야 되는 최소 노드 수

3. 해결 방법

• SCC로 그룹 짓기
• if(scc[i] != scc[next])
  • representative[next] = false;
• 각 도미노를 강한 연결 요소 scc단위로 묶어서 한 번 더 생각하면 됨.

4. 실수한 점, 개선할 점

• 순한 하는 경우 0번 넘어뜨려야 된다는 경우가 나오므로 if(! cnt) 일 경우 cnt=1을 해주어야 한다.
• 0으로 초기화하는 것이 아닌 -1로 초기화하도록 하자.

 

<코드>

#include <iostream>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int MAX_N = 100001;

// <문제>
// 테스트 케이스의 개수 T
int T;
// 도미노의 개수 N, 관계의 개수 M
int N, M;
// 무가중치 방향 그래프
vector<int> adj[MAX_N];

// SCC 알고리즘
int discover[MAX_N], scc[MAX_N];
stack<int> st;
int scc_size, sccCnt;
// 대표 그룹
bool repreGroup[MAX_N];

int dfs(int no) {
    st.push(no);
    // 몇번째로 탐색됐는지 저장
    discover[no] = sccCnt++;
    // 부모를 자기 자신의 번호로 초기화
    int parent = discover[no];
    
    for(auto next : adj[no]) {
        // 아직 탐색되지 않았다면 DFS 탐색
        if(discover[next] == -1)
            parent = min(parent, dfs(next));
        // 이미 탐색했고 scc로 확정되지 않았다면
        else if(scc[next] == -1)
            parent = min(parent, discover[next]);
    }
    
    // 부모와 자기 자신의 번호가 같다면
    if(parent == discover[no]) {
        // 자기 자신이 나올때까지 pop
        while(true) {
            int here = st.top();
            st.pop();
            scc[here] = scc_size;
            if(here == no)
                break;
        }
        scc_size++;
    }
    
    return parent;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    while(T--) {
        // 배열 초기화
        memset(discover, -1, sizeof discover);
        memset(scc, -1, sizeof scc);
        fill(repreGroup, repreGroup + MAX_N, true);
        scc_size = sccCnt = 1;
        for(int i=0; i<MAX_N; i++)
            adj[i].clear();
        
        // <input>
        cin >> N >> M;
        for(int i=0; i<M; i++) {
            int x, y;
            cin >> x >> y;
            adj[x].push_back(y);
        }
        
        // Tarjan Algorithm
        for(int i=1; i<=N; i++) {
            if(discover[i] == -1)
                dfs(i);
        }
        
        // 서로 연결될 수 있는 SCC 제거하기
        for(int i=1; i<=N; i++)
            for(auto next : adj[i])
                // scc가 다를 경우 자연스럽게 넘어지므로 pass
                if(scc[i] != scc[next])
                    repreGroup[scc[next]] = false;
        
        scc_size--;
        int cnt = 0;
        for(int i=1; i<=scc_size; i++)
            if(repreGroup[i])
                cnt++;
        if(!cnt) cnt = 1;
        cout << cnt << '\n';
    }
    
    return 0;
}

 

<SCC 알고리즘>

https://ip99202.github.io/posts/SCC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

SCC 알고리즘

 

<C++ memset()>

https://blockdmask.tistory.com/441

[C언어/C++] memset 함수 메모리 초기화

 

<문제 바로가기>

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

4196번: 도미노

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.