백준 3977. 축구 전술

# 문제 설명

세계 축구 대회의 전술을 짜는 감독 도현이는 자신의 팀이 우승하도록 전략을 짠다.

경기장을 여러 개의 구역으로 나누어, 어떤 선수가 A 구역에서 B 구역으로 움직이는 것을 (A, B)로 표현한다.

도현이는 다른 모든구역에 도달할 수 있는 시작 구역을 찾은 뒤, 이 움직임을 따라가라고 지시한다.

선수들이 시작구역을 찾는 것을 어려워하는데, 가능한 모든 시작 구역을 찾아 오름차순으로 하나씩 출력해라.

단, 그러한 시작구역이 없다면 "Confused"를 출력한다.

 

# 입출력 예시

입력	출력
2 4 4 0 1 1 2 2 0 2 3 4 4 0 3 1 0 2 0 2 3	0 1 2 Confused

 

# 코드 풀이 1.  모든 정점에 대해 DFS 탐색 (타잔 알고리즘)

from collections import defaultdict, deque

T = int(input())
for tc in range(T):
    if tc in range(1, T): 
        input()
    
    n, move = map(int, input().split(' '))
    graph = defaultdict(list)
    for _ in range(move):
        a, b = map(int, input().split(' '))
        graph[a].append(b)
    
    def is_all_visit(s, q, visited):
        while q:
            for y in graph[q.popleft()]:
                if y == s:
                    return True
                elif not visited[y]:
                    visited[y] = True
                    q.append(y)
        return False
    
    flag = True
    for i in range(n):
        q = deque([i])
        if is_all_visit(i, q, [False]*n):
            flag = False
            print(i)
    if flag:
        print('Confused')

 

# 코드 풀이 2.  순방향 & 역방향 그래프가 같으면 SCC (코사라주 알고리즘)

from collections import defaultdict

def dfs(node, visit, stack): # 정방향 DFS
    visit[node] = 1
    for now in graph[node]:
        if visit[now] == 0:
            dfs(now, visit, stack)
    stack.append(node)

def reverse_dfs(node, visit, stack): # 역방향 DFS
    visit[node] = True
    ids[node] = idx # 각 노드의 시작 idx 저장
    stack.append(node)
    for now in reverse_graph[node]:
        if not visit[now]:
            reverse_dfs(now, visit, stack)

# start!
T = int(input())
for tc in range(T):
    if tc in range(1, T): 
        input()
    
    n, move = map(int, input().split(' '))
    graph = defaultdict(list)
    reverse_graph = defaultdict(list)
    for _ in range(move): # 정방향 & 역방향 그래프 초기화
        a, b = map(int, input().split(' '))
        graph[a].append(b)
        reverse_graph[b].append(a)
    
    # 정방향 DFS 순회하면서, stack에 경로 저장
    stack = []
    visit = [False]*n
    for i in range(n):
        if not visit[i]:
            dfs(i, visit, stack)

    
    result = [[] for _ in range(n)] # 각 노드에서 탐색할 수 있는 정점(중복X)
    visit = [False]*n
    idx = -1 # SCC 개수
    ids = [-1] * n
    while stack:
        # pop되는 요소에서 역방향 dfs, scc를 결과에.
        ssc = []
        node = stack.pop()
        if not visit[node]:
            idx += 1
            reverse_dfs(node, visit, ssc)
            result[idx] = ssc
    scc_indegree = [0] * (idx + 1) # SCC 개수
    
    for i in range(n):
        for ed in graph[i]:
            if ids[i] != ids[ed]: # 정점과 연결된 노드들이 같지 않으면(SCC X)
                scc_indegree[ids[ed]] += 1

    cnt = 0
    temp = []
    for i in range(idx+1): # SCC 후보 개수만큼 돌면서
        if scc_indegree[i] == 0: # SCC가 있다면
            for r in result[i]:
                temp.append(r)
            cnt += 1
    
    if cnt == 1: # 모든 구역갈 수 있으면
        for i in sorted(temp):
            print(i)
    else:
        print("Confused")

 

 

# 핵심 포인트

- SCC(Strongly Connected Component)는 방향 그래프에서 어떤 두 정점에 대해 A -> B 로 가는 경로가 항상 존재하는 그룹을 말한다. 이를 푸는 방법은 크게 타잔 알고리즘과 코사라주 알고리즘이 있다.

- 시작 구역은 모든 구역을 방문할 수 있는 구역이어야 한다.

 

참고 자료.

[백준] 3977번 축구 전술 / Java, Python

 

SCC(Strongly Connected Component)