[백준] 9466번: 텀 프로젝트 (DFS|Python) - 그래프에서 cycle을 찾기

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

와 ~~ 상당히 어려운 재귀인 것 같다 

문제를 읽어봤을 때 얻을 수 있는 힌트는 간단하다.

프로젝트 팀이 형성되는 경우는 그래프 구조에서 cycle이 형성되는 상태이다. 따라서 cycle 을 형성하기 위하여 node 들이 이어져있는 관계를 파악해야 한다. 

예를 들어서 문제 예시에서 팀을 이루는 (4, 7, 6) 을 살펴보자. 

1. visited 

node 4를 아직 방문하지 않았으므로 4에 대해 방문처리한다. 그리고 cycle 리스트에 4를 포함시킨다. 

cycle = [4]

0	1	2	3	4	5	6	7
				T

4 는 7을 선택했다. 따라서 dfs(7) 로 넘어가게 된다. 7에 대해 방문처리한다. cycle 리스트에 7을 append한다. 

cycle = [4, 7]

0	1	2	3	4	5	6	7
				T			T

7 은 6을 선택했다. 따라서 dfs(6) 가 실행된다. 6에 대해 방문처리한다. cycle 리스트에 6을 append 한다. 

cycle = [4, 7, 6]

0	1	2	3	4	5	6	7
				T		T	T

6은 4를 선택했다. 그런데 4는 이미 방문처리가 되어있으며, 현재 cycle 이라는 리스트에 담겨져있는 상태이다. 

따라서 cycle list 에 있는 4 부터 현재 cycle에 담겨져있는 마지막 원소까지가 현재 cycle을 형성하고 있으므로 하나의 프로젝트 팀이 된다. 

# https://www.acmicpc.net/problem/9466
import sys
sys.setrecursionlimit(10**6)

def dfs(node):
    global data, visited, cycle
    visited[node] = True
    cycle.append(node)
    if visited[data[node]]: # 이미 방문 했으면
        if data[node] in cycle:
            team.extend(cycle[cycle.index(data[node]):])
    else:
        dfs(data[node])


T = int(input())
for _ in range(T):
    N = int(input()) # 학생의 수
    visited = [False] * (N+1)
    data = [0] + list(map(int, input().split()))
    edge = [[] for _ in range(N+1)]
    team = [] # 팀에 속하게 된 학생 목록

    for i in range(1, N+1):
        if not visited[i]:
            cycle = []
            dfs(i)

    # 팀에 속하지 못한 학생 수
    print(N - len(team))