백준 4196번: 도미노 (Python)

접근

처음엔 왜 이것이 SCC 문제인가 고민을 했었다. 가장 기본적으로는 도미노의 시작점을 찾아야 하기 때문에 위상 정렬을 쓰는 것이 맞고, 추가적으로 그 사이에 SCC 를 이루는 노드들이 있을 경우 이 한덩이의 SCC 를 한개의 노드 취급을 해서 계산을 하면 옳게 풀 수 있다. 특히 SCC 를 적용하지 않을 경우 원형의 싸이클을 이루는 하나의 SCC 의 예를 들었을 때, 일반적으로 위상 정렬에 쓰는 indegree 값이 0 인 노드가 존재하지 않을 수 있다. 또한 같은 이유로 indegree 가 0 인 노드 수와 도미노 시작점의 수가 일치하지 않을 것이다.

결론적으로 풀이 방법을 보면,

1. 전체 그래프에서 SCC 를 구한다.
2. SCC 들을 기준으로 진입점인 indegree 를 계산해주고,
3. indegree 값이 0 인 노드들과 SCC 들을 찾아 카운트 해주면 도미노의 시작점을 찾을 수 있다.

아래 코드에서는 코르사주 알고리즘을 이용하여 SCC 를 구할 수 있었다.

SCC 알고리즘 설명 및 기본 문제: 2021.07.10 - [코딩/백준 (Python)] - 백준 2150번: Strongly Connected Component (Python)

백준 2150번: Strongly Connected Component (Python)

코드

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(node, visited, stack):
    visited[node] = 1
    for ne in graph[node]:
        if visited[ne] == 0:
            dfs(ne, visited, stack)
    stack.append(node)


def reverse_dfs(node, visited, scc):
    global idid
    visited[node] = 1
    ids[node] = idid
    scc.append(node)
    for ne in reverse_graph[node]:
        if visited[ne] == 0:
            reverse_dfs(ne, visited, scc)


t = int(sys.stdin.readline())
for _ in range(t):
    v, e = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(v + 1)]
    reverse_graph = [[] for _ in range(v + 1)]
    for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        reverse_graph[b].append(a)
    stack = []
    visited = [0] * (v + 1)
    for i in range(1, v + 1):
        if visited[i] == 0:
            dfs(i, visited, stack)
    idid = 0
    ids = [-1] * (v + 1)
    visited = [0] * (v + 1)
    result = []
    while stack:
        ssc = []
        node = stack.pop()
        if visited[node] == 0:
            idid += 1
            reverse_dfs(node, visited, ssc)
            result.append(sorted(ssc))
    scc_indegree = [0] * (idid + 1)
    for i in range(1, v + 1):
        for to in graph[i]:
            if ids[i] != ids[to]:
                scc_indegree[ids[to]] += 1
    cnt = 0
    for i in range(1, len(scc_indegree)):
        if scc_indegree[i] == 0:
            cnt += 1
    print(cnt)

더 생각해 볼 것?

문제를 풀기 위해 여러가지 방법을 시도하다가 정답을 받은 코드 중에 반례가 있는 것 같아 데이터 추가 요청을 해두었다. 이 반례가 문제의 의도에 맞는지는 모르고, 또한 이 데이터 추가 요청이 받아들여질 지는 모르겠지만, 이후 변동사항이 확인되면 다시 수정할 예정이다.

정답 받은 코드

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(x, low, ids, visited, stack):
    global idid
    ids[x] = idid
    low[x] = idid
    idid += 1
    visited[x] = 1
    stack.append(x)
    for ne in graph[x]:
        if ids[ne] == -1:
            dfs(ne, low, ids, visited, stack)
            low[x] = min(low[x], low[ne])
        elif visited[ne] == 1:
            low[x] = min(low[x], ids[ne])
    w = -1
    scc = []
    if low[x] == ids[x]:
        while w != x:
            w = stack.pop()
            scc.append(w)
            visited[w] = -1
        result.append(sorted(scc))


t = int(sys.stdin.readline())
for _ in range(t):
    n, m = map(int, sys.stdin.readline().split())
    graph = [[] for ___ in range(n + 1)]
    indegree = [0] * (n + 1)
    for __ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        indegree[b] += 1
    cnt = 0
    stack = []
    idid = 0
    result = []
    ids = [-1] * (n + 1)
    low = [-1] * (n + 1)
    visited = [0] * (n + 1)
    for i in range(1, n + 1):
        if ids[i] == -1:
            dfs(i, low, ids, visited, stack)
    for scc in result:
        if len(scc) == 1:
            if indegree[scc[0]] == 0:
                cnt += 1
        else:
            tmp = True
            for j in scc:
                if indegree[j] > 1:
                    tmp = False
            if tmp:
                cnt += 1
    print(cnt)

정답을 받았던 위 코드에서는, 한개의 scc 에 속한 요소들의 indegree 값이 1을 넘어가면 해당 scc 는 외부에서 오는 진입점이 있는 것으로 생각하고 반대로 모든 요소가 indegree 값으로 1 을 가지면 진입점이 없는 scc 라고 판단하여 도미노의 시작점을 한개 카운트 해주었다. 이런 식으로 풀었던 풀이로 정답을 받았으나 아래와 같은 경우에 오류가 발생함을 우연히 알 수 있었다.

[input]
1
5 6
1 2
2 3
3 1
1 4
4 5
5 1

[output]
0

[answer]
1

위와 같은 경우 5개의 노드 모두 한개의 scc 로 묶이는 것을 알 수 있다. 하지만 코드에 넣어보면 0을 출력한다. 당연하게도 1개 이상 건드려주어야 도미노가 무너지므로 이는 답이 아니다. 새로운 풀이를 생각하여 본문의 풀이대로 코딩하였고 정답을 받았으며, 위의 반례에도 정확히 1을 출력해준다.

코드가 지저분하여 다시 정리할 필요성은 느껴진다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!