[BOJ/백준] 9466 텀 프로젝트

# # # 9466 텀 프로젝트
import sys
sys.setrecursionlimit(100000)
 
 
 
def dfs(node):
    global result
    visited[node] = False
    total.append(node)
    next_node = graph[node]
    if not visited[next_node]:
        if next_node in total:
            find_index = total.index(next_node)
    
            result +=total[find_index:]
        return
    else:
        dfs(next_node)
 
 
for _ in range(int(input())):
    N = int(input())
    graph = [0]+list(map(int,sys.stdin.readline().split()))
    visited = [True] *(N+1)
    result = []
    for ind in range(1,N+1):
        if visited[ind]:
            total = []
            dfs(ind)
    print(N-len(result))

 

문제를 풀때, 어떻게 풀어야할지 고민을 했던 문제이다. 문제를 읽어보면, 사이클을 이루는 경우에만, 팀이 될수 있다는 것을 알 수 있다. 

그래서 DFS 재귀를 통해서, 내가 방문한 곳을 다시 방문하게 된다면, 사이클을 이루게 되는 것이기 때문에, 결과값에 추가해주었다. 중간의 find_index 같은 경우 사이클을 이루어지는 최초지점을 찾아서 저장해주기 위함이다.

 

만약 1,2,3,4,5 가 있고, 각각 2,3,4,5,2를 선택했다고 하면 dfs를 했을때 total에는 [1,2,3,4,5]가 저장되어있을 것이다. 하지만, 1은 문제에 주어진 조건을 만족하지 못하고, 팀이 되지 못한다. 그래서 사이클이 최초로 시작되는 2를 기준으로 잘라주기 위함이다.

 

for _ in range(int(input())):
    N = int(input())
    graph = list(map(int,input().split()))
    visited = [0]*N
    cnt = 0
    for current_node in range(N):
        if not visited[current_node]:
            next_node = current_node
            while visited[next_node] == 0:
                visited[next_node] = 1
                next_node = graph[next_node] - 1
            cycle_index = current_node
            while cycle_index != next_node:
                cnt += 1
                cycle_index = graph[cycle_index] - 1
 
    print(cnt)
 

좀 더 깔끔한 풀이다. 위와 비슷하지만, 최초로 사이클이 시작되는 노드는 중간의 while문을 통과하고 나온 next_node일것이다.

그러면 처음 노드인 current_node를 복사해, cycle_index라고 하고, 이 cycle_index가 next_node와 같지 못하면, 사이클에 포함되지 않는 노드임을 알 수 있다. 이 next_node는 사이클이 최초로 발생하는 노드의 위치이기 때문에, 만약 current_node에서 사이클이 시작됬다면 cycle_node와 next_node는 동일할 것이다. 

그래서, 이 cycle_node를 똑같이 반복문을 돌리면서 next_node와 같아질때까지 반복을 한다. 그게 곧 팀에 포함되지 않는 사람의 수를 나타내는 것임을 알 수 있다.