[DFS, BFS] 백준 9466번 : 텀 프로젝트 / 골드 3

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

9466번: 텀 프로젝트

import sys
input = sys.stdin.readline

tc = int(input())
for _ in range(tc):
    n = int(input())
    lst = list(map(int, input().split()))

    visited = [False for _ in range(n)]
    cycle = [False for _ in range(n)]

    for i in range(n):
        if visited[i]:
            continue

        visited[i] = True
        cur = i
        order = [cur]
        while True:
            next = lst[cur]-1
            if visited[next]:
                if next not in order:
                    break
                else:
                    j = order.index(next)
                    for k in range(j, len(order)):
                        cycle[order[k]] = True
                    break

            visited[next] = True
            order.append(next)
            cur = next

    print(n-sum(cycle))

확신없이 일단 제출을 해봤는데 한번에 통과가 되어 당황한 문제.

 

12번째줄 코드부터 진행 방식은 대략 다음과 같다.

O(N)짜리 반복문을 돈다. 노드 번호는 i 로 설정. (인덱스임을 헷갈리지 않도록 주의)

방문체크가 되어있으면 통과, 안되어있으면 계속 진행.

i을 cur로 설정하고 order 리스트를 만들어 cur를 담아준다.

그리고 while 문 안에 들어가서,

next 노드를 꺼내와서 

next 노드가 방문 체크가 안되어있으면? -> 방문체크 + order 리스트 안에 추가

next 노드가 방문 체크가 되어있으면? -> order 안에 이 next가 들어있다면 싸이클을 발견한 것이고, 안에 없다면 이미 탐색을 완료한 노드임.

싸이클을 발견했다면 order 안에 next의 위치를 찾아 끝까지 탐색하면서 해당 노드의 싸이클 여부를 True로 설정해주면 된다.