백준_9466_텀 프로젝트

문제

9466번: 텀 프로젝트

풀이

1) 사이클 찾기

모든 학생들을 시작점으로 두고 dfs를 통해 사이클을 탐색한다. 

1. 기존에 방문하지 않은 학생이라면,

• 방문기록을 남긴다.
• 다음 학생으로 이동한다.

2. 기존에 방문한 학생이라면, 방문 경로를 찾아 사이클을 이루는 학생의 수를 반환한다.

2) 시간초과

시간초과로 오래 고민했던 문제인데, 다른 문제를 풀면서 다시 한번 도전했다. 

코드

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

def dfs(n) :
    if n == END :
        cnt = 0
        n = visited.pop()
        for pre in visited[::-1] :
            cnt += 1
            if pre == n : return cnt
        return False

    nxt, student[n] = student[n], END  # visited
    visited.append(n)
    return dfs(nxt)

END = 0
visited = list()

for t in range(int(input().strip())) :
    N = int(input().strip())
    student = list(map(int, input().strip().split()))
    student = [END] + student
    cnt = 0

    for i in range(N) :
        visited.clear()
        cnt += dfs(i+1)

    print(len(student) - cnt - 1)

마무리

사이클을 찾는 문제로, 아래의 문제와 유사한 풀이를 사용했다. 

2022.10.04 - [코딩테스트/백준] - 백준_16724_피리 부는 사나이