[백준 4196번] 도미노 (Python3)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def DFS(now):
  global id
  stack.append(now)
  visited[now] = nowid = id
  for next in graph[now]:
    if not visited[next]:
      id += 1
      DFS(next)
    if visited[next] <= nowid:
      indegree[next] -= 1
      visited[now] = min(visited[now],visited[next])
  if visited[now] == nowid:
    scc.append([]); sccindegree.append(0)
    while 1:
      x = stack.pop()
      scc[-1].append(x)
      sccindegree[-1] += indegree[x]
      visited[x] = 1e7
      if x == now:
        break
        
for _ in range(int(input())):
  N,M = map(int,input().split())
  
  graph = [[] for i in range(N)]; indegree = [0]*N
  for _ in range(M):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    indegree[b-1] += 1
  
  visited = [0]*N
  stack,scc,sccindegree = [],[],[]
  for i in range(N):
    if not visited[i]:
      id = 1
      DFS(i)
  print(sccindegree.count(0))

위상정렬 + SCC로 해결하였다.

처음에는 그냥 위상정렬 문제라고 생각했다. 위상정렬으로 indegree가 0인 도미노를 찾고, 전부 넘어뜨려 본 뒤(indegree가 0이면 다른 도미노에 의해 넘어질 수가 없으므로 무조건 넘어뜨려야한다) 만약 도미노가 남아있다면 나머지 도미노는 랜덤으로 넘어뜨리는 방식으로 풀었다.

그러나 이 방법은 틀렸습니다 가 떴다. 이유는 금방 생각해낼 수 있었다. indegree가 0인 도미노를 모두 넘어뜨리고 나면 SCC를 이루는 도미노만 남게 되는데, SCC간에도 먼저 넘어뜨려야하는 순서가 있기 때문이다.

 

따라서 "SCC의 indegree"를 구하는것이 이 문제의 핵심 포인트이다.

풀이를 설명하면,

1. 도미노의 관계에 따라서 도미노의 그래프와 indegree를 저장한다.

2. 타잔 알고리즘으로 SCC를 찾는다. SCC를 구하면서 각 SCC의 indegree도 구해준다.

(SCC의 indegree란, 같은 SCC 요소간의 indegree를 제외한 모든 요소의 indegree의 합을 의미한다)

3. indegree가 0인 SCC의 개수를 출력한다.

 

 

오늘의 교훈) SCC 알고리즘을 활용해서 다양한 문제를 해결하자