[Python/파이썬] 백준 9466번: 텀 프로젝트

문제

 

풀이

사이클을 판별하는 문제이다.

 

1. 문제에서 주어진 배열을 parent 배열이라 하자.

 

2. 사이클을 판별하기 위해 이때까지 방문한 노드를 cycle 배열에 저장,

방문 처리를 위해 visited 배열을 생성

 

3. 1번 노드를 방문했을 때

 

4. 1번 노드와 연결된 3번 노드 방문

 

각 노드를 방문하고, 그 노드와 이어진 노드를 계속 방문한다.

만약 이미 방문한 노드이고 사이클 배열에 해당 노드가 존재하면 사이클이 형성되었다는 것이다.

 

위 과정을 직접 해보면 이해가 쉽다.

 

코드

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

def dfs(st):
    global team
    visited[st] = True
    cycle.append(st)
    
    next = parent[st]
    if visited[next]:
        if next in cycle:
            team += len(cycle[cycle.index(next):])
        return
    
    dfs(next)

t = int(input())

for _ in range(t):
    n = int(input())
    parent = [0] + list(map(int, input().split()))
    visited = [False] * (n + 1)
    team = 0
    for i in range(1, n + 1):
        if not visited[i]:
            cycle = []
            dfs(i)
    print(n - team)

 

마무리

삽질하다가 도저히 모르겠어서 구글링 했다..

사이클 판별... 어렵다.

이해는 했지만 완전히 내 걸로 만들진 못했다.