9466번 텀 프로젝트

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

---

아이디어

처음에 생각했던 아이디어는 visited를 2차원으로 만들어서 [0]에는 현재 방문했는지 여부, [1]에는 사이클이 발생했는지 여부를 했었다. 하지만 현재 방문했는지를 하다보니 새로운 노드를 돌 때마다 모든visited[0]을 초기화 해서 시간복잡도 O(n^2)이 나와 아래와 같이 시간초과가 나왔다.

그래서 생각한 것은 visited는 리스트로 방문했는지 여부만 관리했다. 사이클인지 아닌지는 지나간 노드들을 path라는 리스트에 넣고 이미 방문했는데 또 방문했다면(x노드) path 리스트 안에 처음으로 나온 x부터 끝까지 cycle이라는 말이다. 문제에서 팀을 못 만든 인원을 구하라고 했으므로 전체 인원 수에서 cycle이 만들어진 명수만 빼면 된다.

---

코드

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

def dfs(node):
    global cnt
    path.append(node)
    visited[node] = 1
    x = graph[node] # 현재 노드가 신호 보내는 노드
    if visited[x] == 0:
        dfs(x)
    elif x in path: # 사이클 발생
        cycle_start = path.index(x) # 사이클 시작 노드
        cnt -= len(path[cycle_start:]) # 사이클 노드 개수 빼기
    path.pop()
    return


T = int(input())
for _ in range(T):
    n = int(input()) # 학생 수
    graph = [0]+list(map(int, input().split()))
    visited = [0]*(n+1)
    path = []

    cnt = n
    for i in range(1, n+1):
        if visited[i] == 0: # 방문 안했다면
            path = []
            dfs(i)

    print(cnt)