백준 3977번: 축구 전술 (Python)

접근

이전 문제와 마찬가지로 SCC 문제로 분류되어 있기는 하지만 위상 정렬이 더 큰 비중을 차지하는 문제였다.

SCC 를 먼저 탐색하여 SCC 에 속하는 위치들끼리는 하나의 노드처럼 생각하고 위상정렬에서와 같이 진입점(indegree)가 0 인 노드 혹은 SCC 를 찾는 문제이다. 이전 문제와 동일하게 풀되, 다른 점은 이전 도미노 문제에서는 시작점의 최소 개수만 체크했다면, 이번 문제에서는 시작점이 될 수 있는 요소들을 찾고 만약 그 시작점이 여러개거나 없다면 선수가 시작점을 헷갈릴 수 있기 때문에 Confused 를 출력해주면 된다.

즉,

1. indegree 가 0 인 노드가 1개 있다: 해당 노드를 출력
2. indegree 가 0 인 SCC 가 1개 있다: 해당 SCC 에 속하는 노드들을 오름차순으로 출력
3. indegree 가 0 인 노드 혹은 SCC 가 0개 혹은 2개 이상 있다: Confused 출력

위와 같이 구분하여 출력해주면 된다.

SCC 와 위상정렬을 이용하는 도미노 문제: 2021.07.11 - [코딩/백준 (Python)] - 백준 4196번: 도미노 (Python)

백준 4196번: 도미노 (Python)

코드

import sys
sys.setrecursionlimit(10 ** 6)


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


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


t = int(sys.stdin.readline())
while t:
    income = sys.stdin.readline()
    if income == '\n':
        continue
    n, m = map(int, income.split())
    graph = [[] for _ in range(n)]
    reverse_graph = [[] for _ in range(n)]
    for __ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        reverse_graph[b].append(a)
    stack = []
    visited = [0] * n
    for i in range(n):
        if visited[i] == 0:
            dfs(i, visited, stack)
    idid = -1
    ids = [-1] * n
    visited = [0] * n
    result = [[] for __ in range(n)]
    while stack:
        scc = []
        node = stack.pop()
        if visited[node] == 0:
            idid += 1
            reverse_dfs(node, visited, scc)
            result[idid] = scc
    scc_indegree = [0] * (idid + 1)
    for i in range(n):
        for to in graph[i]:
            if ids[i] != ids[to]:
                scc_indegree[ids[to]] += 1
    tmp = []
    cnt = 0
    for i in range(len(scc_indegree)):
        if scc_indegree[i] == 0:
            for j in result[i]:
                tmp.append(j)
            cnt += 1
    if cnt == 1:
        for i in sorted(tmp):
            print(i)
    else:
        print("Confused")
    print()
    t -= 1

더 생각해 볼 것?

코드가 지저분하여 정리할 필요가 있는 것 같다.

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