[BOJ] 백준 3977 축구 전술 Python

3977번: 축구 전술

문제
World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다. 모든 도현이의 팀 선수들이 이 움직임만을 따라서 이동한다면 승리하리라고 도현이는 확신한다.
도현이는 선수들에게 자신의 전술을 말해주며, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그러나 도현이는 한 가지 간과한 것이 있었는데 그건 선수들이 자신만큼 똑똑하지 않다는 것이다. 선수들은 그러한 시작 구역을 찾는 것이 어려웠다. 이제 당신이 적절한 시작 구역을 찾아줘야 한다.

입력
첫 번째 줄에 테스트 케이스의 개수가 주어지며, 이는 11보다 작거나 같은 정수이다.
그 다음 줄부터 여러 개의 테스트 케이스가 주어지는데, 각 테스트 케이스마다 첫 번째 줄에 구역의 수 N, 지시한 움직임의 수 M이 주어지며 1 ≤ N, M ≤ 100,000 이다. 그 다음 M개의 줄에 걸쳐서 움직임 (A, B)가 주어지며, A, B는 0 ≤ A, B < N인 정수이다.
각 테스트 케이스는 하나의 빈 줄로 구분된다.

출력

각 테스트 케이스마다 가능한 모든 시작 구역을 오름차순으로 한 줄에 하나씩 출력한다. 만약 그러한 시작 구역이 없으면, "Confused"를 출력한다.

각 테스트 케이스의 끝에는 하나의 빈 줄을 출력한다.

---

문제풀이
처음 문제 상황과 입력예시만 보고 접근했을때 그래프에서 사이클 판별을 통해 사이클이 있다면 루프 연결 요소를 출력하고 아니라면 Confused를 출력하는 식으로 풀이하였다. 하지만 코드를 제출했을 때 출력 초과가 나왔고 완전한 해결책을 찾지 못한채 다른 분들의 풀이와 알고리즘을 참고하였다.

다시 본론으로 돌아가 이 문제는 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다고 할 때, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾아내는 문제이다.

SCC, Strongly Connected Component는 방향이 있는 그래프에서 서로 강하게 연결되어있는 부분집합을 의미한다.
'강하게 연결되었다' 라는 말은 하나의 사이클이 존재한다는 것이다.
SCC를 찾는 알고리즘 중 하나인 코사라주 알고리즘을 사용해서 문제를 해결했다.
코사라주 알고리즘 순서는 다음과 같다.
1. 주어진 방향그래프의 역방향 그래프를 만든다.
2. 정점을 담을 스택을 만들고 임의의 정점부터 DFS를 수행.
3. DFS가 끝나는대로 스택에 삽입하고, 방문하지 않은 정점에 대해 DFS 수행
4. 모든 정점이 스택에 담긴후에는 스택을 pop하여 나오는 정점부터 역방향 그래프에서 DFS를 수행한다. 이 때 이미 방문한 정점은 pop만 수행한다.
5. 이 때 탐색되는 모든 정점을 SCC로 묶고 이를 스택이 빌때까지 수행한다.

[Algorithm] SCC, Strongly Connected Component 강한연결요소

---

Code

import sys
from sys import stdin

sys.setrecursionlimit(10 ** 6)
input = stdin.readline


""" 정방향 DFS """ 
def dfs(start, visited, stack):
    visited[start] = True
    for now in graph[start]:
        if not visited[now]:
            dfs(now, visited, stack)
    stack.append(start)


""" 역방향 DFS """
def rev_dfs(start, visited, stack):
    visited[start] = True
    ids[start] = idx
    stack.append(start)
    for now in rev_graph[start]:
        if not visited[now]:
            rev_dfs(now, visited, stack)


test_case = int(input())
while test_case:
    tmp_line = input()
    if tmp_line == '\n':
        continue
    N, M = map(int, tmp_line.split())
    graph = [[] for _ in range(N)]
    rev_graph = [[] for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)
        rev_graph[b].append(a)
    stack = []
    visited = [False] * N

    for i in range(N):
        if not visited[i]:
            dfs(i, visited, stack)
    result = [[] for _ in range(N)]
    visited = [False] * N
    idx = -1  
    ids = [-1] * N  

    while stack:
        """ pop되는 정점에서 rev_DFS하고 SCC를 result 배열에 추가 """
        scc = []
        node = stack.pop()
        if not visited[node]:
            idx += 1
            rev_dfs(node, visited, scc)
            result[idx] = scc
    scc_connected = [0] * (idx + 1)

    for i in range(N):
        for j in graph[i]:
            if ids[i] != ids[j]:
                scc_connected[ids[j]] += 1
    cnt = 0
    tmp = []
    for i in range(len(scc_connected)):
        if scc_connected[i] == 0:
            for asw in result[i]:
                tmp.append(asw)
            cnt += 1
    if cnt == 1:
        for i in sorted(tmp):
            print(i)
    else:
        print("Confused")
    print()
    test_case -= 1