플레티넘4
문제 4196
정답
## 도미노
import sys
sys.setrecursionlimit(10**6)
### 재귀를 사용해서 풀어야 하는 문제라면 이렇게 쓰는 것은 필수이다.
### 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이다.
### 따라서 재귀로 문제를 풀 경우 드물지 않게 이 제한에 걸리게 된다. 이 함정에 걸린 사람은 원인 미상의 런타임 에러를 붙잡고 있게된다.
input = sys.stdin.readline
# 정방향 dfs, dfs 가 종료되는 노드를 stack에.
def dfs(node, visit, stack):
visit[node] = 1
for now in graph[node]:
if visit[now] == 0:
dfs(now, visit, stack)
stack.append(node)
# 역방향 dfs, 탐색하는 순서대로 stack에.
def reverse_dfs(node, visit, stack):
visit[node] = 1
ids[node] = idx
stack.append(node)
for now in reverse_graph[node]:
if visit[now] == 0:
reverse_dfs(now, visit, stack)
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
reverse_graph = [[] for _ in range(N + 1)]
for _ in range(M):
x, y = map(int, input().split())
# 정방향 그래프, 역방향 그래프 추가
graph[x].append(y)
reverse_graph[y].append(x)
stack = []
visit = [0] * (N + 1)
# 모든 노드에서 dfs를 수행.
for i in range(1, N + 1):
if visit[i] == 0:
dfs(i, visit, stack)
idx = 0
ids = [-1] * (N + 1)
visit = [0] * (N + 1)
result = []
while stack:
# pop되는 요소에서 역방향 dfs, scc를 결과에.
ssc = []
node = stack.pop()
if visit[node] == 0:
idx += 1
reverse_dfs(node, visit, ssc)
result.append(sorted(ssc))
scc_indegree = [0] * (idx + 1)
for i in range(1, N + 1):
for ed in graph[i]:
if ids[i] != ids[ed]:
scc_indegree[ids[ed]] += 1
cnt = 0
for i in range(1, len(scc_indegree)):
if scc_indegree[i] == 0:
cnt += 1
print(cnt)풀이
아직 공부가 부족해서 위상 정렬이나, SCC에 관해 이해가 쉽지 않다. 3개의 풀이 모두 같은 방식을 말하고 있지만, 이해를 더 쉽게 받아들이기 위해 여러 설명들을 참고하여 작성했다.
해설 1
SCC와 약간의 위상 정렬 방법(indegree[] 배열)을 이용해서 푸는 문제이다.
도미노의 시작점을 찾아야 하기 때문에 위상정렬을 쓰는 것이 맞고, 추가적으로 그 사이에 SCC를 이루는 노드들이 있을 경우 하나의 SCC를 한개의 노드 취급을 해서 계산을 하면 옳게 풀 수 있다.
특히 SCC를 적용하지 않을 경우 원형의 싸이클을 이루는 하나의 SCC의 예를 들었을 때, 일반적으로 위상 정렬에 쓰는 indegree 값이 0인 노드가 존재하지 않을 수 있다. 또한 같은 이유로 indegree가 0인 노드 수와 도미노 시작점의 수가 일치하지 않을 것이다.
[과정]
1. 전체 그래프에서 SCC를 구한다.
2. SCC들을 기준으로 진입점인 indegree를 계산해주고,
3. indegree값이 0인 노드들과 SCC들을 찾아 카운트 해주면 도미노의 시작점을 찾을 수 있다.
해설 2
과정
1. 블록끼리의 연결을 가지고, kosaraju algorithm을 이용해 SCC를 구한다.
kosaraju algorithm : 2번의 dfs를 이용, stack을 활용
2. SCC끼리의 연결 상태를 저장한다.
ex) SCC 1 -> SCC 2로 연결이 가능하다면 SCC 2의 indegree(들어오는 간선 수)를 +1 시켜준다.
3. SCC 중 indegree 값이 0인 SCC의 개수를 세어서 출력한다.
총 SCC 개수는 2개이고, indegree가 0인 SCC는 1개니까 결론적으로 손으로 넘어트려야 하는 블록의 최소 개수는 1개이다.
indegree가 1개 이상인 SCC에 속한 블록들은 다른 SCC 블록들에 의해 넘어질 수 있다고 생각하면 된다.
해설 3
[(힌트)
도미노를 그래프로 모델링하면 위상 정렬을 통해 진입 차수가 0인 노드의 개수를 세는 방법으로 접근할 수 있다. 하지만 이것으로는 부족하다. 도미노의 상태에 따라 사이클이 생성될 수도 있고 그렇지 않을 수도 있다.
빨간색으로 표시된 아무 도미노나 넘어트리면 모든 도미노를 넘어뜨릴 수 있다. 사이클을 영리하게 이용하는 방법을 생각해본다.]
최소한의 시행으로 모든 도미노를 넘어뜨리기 위해서는 indegree가 0인 도미노만 건드려야 한다.
하지만 위에 힌트에서도 언급했듯이 어떤 도미노 집합이 사이클을 이루고 있는 경우에는 indegree가 0인 도미노가 없지만 해당 사이클에서 아무 도미노나 넘어뜨려도 모든 도미노를 넘어뜨릴 수 있다.
즉 우리는 도미노 각각의 indegree만 계산할 것이 아니라 사이클의 indegree도 계산해야 한다.
이를 효율적으로 계산하기 위해서는 SCC를 구해서 각 SCC의 indegree를 계산하도록 하면 된다.
구현하는 방법은 SCC를 구한 뒤 각 노드마다 해당하는 SCC 번호를 붙여준다.
그 다음 한 번 더 DFS를 수행해서 현재 노드와 자식 노드의 SCC 번호가 같지 않을 때 자식에 속한 SCC의 indegree를 1 더해주면서 각 SCC의 indegree를 구할 수 있게 된다.
이렇게 indegree를 모두 구한 후 indegree가 0인 SCC의 갯수를 출력하면 된다.
