[BOJ 4196]

문제 바로가기 : https://www.acmicpc.net/problem/4196
비슷한 유형 문제, BOJ 3977 : https://www.acmicpc.net/problem/3977
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

review

SCC 응용 문제로 분류되고 있는 도미노 문제다. SCC 기본 문제랑 개념만 익히고 막 시작했을 땐 좀 당황스러웠다.
TC에서는 1->2, 2->3 의 관계를 나타내고 있어서 사이클이 발생하지 않는다. 1을 톡 치면 모든게 우르르 무너져서 답은 1이다.
좀 난감했던 부분은 ‘사이클’이 발생하지 않는데 왜 SCC 문제로 분류되는지였다. 하지만 전에 참고했던 글에서 이런 내용이 있었다.

SCC 알고리즘은 그 자체로 의미가 있다기 보다는 위상 정렬과 같이 응용되는 경우가 많습니다.

위상 정렬은 노드들 간의 순서가 정해져 있을 때 이를 정해진 순서(규칙)대로 정렬하는걸 말한다. 사이클이 발생하면 안된다.
사이클이 발생한다면 이를 한 집단으로 묶고 또 발생하면 묶어서(SCC) 위상 정렬을 수행하면 되겠다는 생각이 들었다.
그리고 BOJ 2150의 TC를 참고하면 알겠지만 노드 단 1개도 SCC가 될 수 있다.
그럼 이 문제의 TC에서는 사이클이 발생하지 않으므로 1, 2, 3이 각각 SCC가 된다고 보면 되겠다. 그럼 위상 정렬을 적용할 수 있다.

적용하기 전에 왜 적용하는지 이유를 잘 모른다면 충분히 생각해볼 필요가 있다. 왜 위상 정렬을 이용해야 할까?
도미노는 시작 지점에서 톡 치면 연결된 도미노가 우르르 쓰러진다. 그리고 연결되지 않은 부분에서 멈추게 된다.
여기서 연결되지 않은 부분을 또 다른 SCC라 착각하기 쉽다. 아래 예가 반례다.

1 2
2 3
3 1
1 4

1, 2, 3은 사이클을 이룬다. 그럼 SCC는 [1, 2, 3], [4]가 된다.
근데 1을 톡 치면 2와 4가 같이 무너진다. SCC가 다르다고 독립됐다고 보면 안된다.

그럼 어떻게 접근해야 맞는걸까? SCC가 구분되는게 의미가 없어 보이겠지만 그렇지 않다. 잘 생각해보자.
1을 치면 2는 물론이고 4도 무너지지만, 2와 3은 쳐도 4가 무너지지 않는다. 1이 무너져야 한다.
그래서 나는 1처럼 다른 SCC와 연결 돼있는 녀석이 parent가 돼야 한다고 생각했다. 근데 이놈을 정하는 기준이 쉽지 않다.
숫자가 제일 작은걸 하자니 노드의 번호가 다르면 그게 곧 반례가 된다.
그렇다고 인풋을 뒤져서 많이 연결된걸 찾을 수도 없다. 당연히 시간 초과 당한다.

union-find처럼 부모 스스로가 집합의 대표가 되는 것도 좋겠지만, 집합의 번호를 할당해주는 것도 방법이다.
그래서 아래와 같이 sccnum으로 집합 번호를 지정해주고, 속한 노드들을 uni[]에 적어줬다.

int dfs(int cur){
  ...
  //부모일 때 하나의 SCC 생성
   if (chk[cur] == parent) {
       vector<int> subSCC;
       sccnum++; //집합 번호는 1부터 시작
       while (1) {
           int node = s.top(); s.pop();
           subSCC.push_back(node);
           fin[node] = true;
           uni[node] = sccnum; //어디 집합에 속했는지
           if (chk[node] == parent) break;
       }
       SCC.push_back(subSCC);
   }

   return parent;
}

그럼 다시 돌아와서 TC를 생각해보자. SCC는 [1, 2, 3], [4]로 구분된다.
간단하게 집합 번호로 구분하면 [1], [2]가 된다. SCC로 묶으니 훨씬 간단해졌다! 관계는 [1]->[2]이다.
위상 정렬에서는 degree가 0이 될 때 큐에 넣어서 진행했다. 0이 되는 녀석이 없으면 사이클이 발생한다는 말이 된다.
하지만 SCC로 묶어버렸으니 사이클은 존재하지 않고, 0이 되는 녀석이 반드시 존재한다!
그럼 0이 되는 얘들이 스타트를 끊는다는 말인데 그 횟수만큼 도미노를 건드려야 된다는걸 알 수 있다.

//answer
for (int i = 1; i <= V; i++) {
    for (auto& next : node[i]) {
        if (uni[i] == uni[next]) continue; //same union
        degree[uni[next]]++;
    }
}

int ans = 0;
for (int i = 1; i <= sccnum; i++)
    if (degree[i] == 0) ans++;

cout << ans << '\n';