SCC. [4196]

[1. 문제 설명]

도미노 블록의 배치가 그래프 형태로 주어졌을 때,

모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최소값을 출력한다.

---

[2. 풀이 접근]

A. 잘못된 접근

• dfs 를 수행하면 현재 블록을 기준으로 넘어 질 수 있는 블록들이 모두 방문된다.
• 이러한 점을 이용하여, dfsAll() 을 실행하여 호출 될 수 있는 dfs() 횟수를 출력한다.
• 이 풀이가 틀린 이유는 아래와 같은 경우처럼, 최초 dfs 호출 대상에 따라 답이 바뀌기 때문이다.

B. 올바른 접근

• 모든 정점을 SCC 로 묶는다.
• 이 SCC 속한 블록들은 어떤 블록을 선택하더라도 모두 넘어지게 된다.
• 이 SCC 에서 다른 SCC 로 연결된 경우를 고려한다.
• 이 SCC 를 수동으로 넘어뜨린 경우, 연결된 SCC 에 속한 블록들도 같이 넘어진다.
• 이러한 넘어짐은 각 SCC 가 연결 된 경우 연쇄적으로 발생하게 된다.
• 최초 수동으로 넘어뜨려야 하는 블록들은 아래와 특성을 갖는다.
• scc 를 정점으로 하는 그래프에서 incoming edge 개수가 없는 scc 에 속한다.

위 풀이에서 몇가지 실수했던 부분은

scc 간 연결성의 확인을 scc 를 찾는 과정에서 수행하려 했다는 것이다.

• 풀이에 실패한 이유는 정확하지 않지만 아래와 같다 생각함 .
• 여러 SCC 에 연결 될 수 있으나, 반드시 하나의 SCC 에 만 연결된다고 생각했던 것.

모든 scc 를 찾고 난뒤, 연결성을 따져도 시간적으로 큰 무리가 없다.

• 모든 edge 에서 각 정점이 서로다른 scc 에 속해있는지만 보면 된다.

---

[3. 코드]