[BOJ] 9466. 텀 프로젝트(🥇, DFS)

문제

풀이

풀이1(시간초과)

• 반드시 현재 출발하는 숫자로부터 사이클이 완벽하게 완성되는 경우에만 탐색을 인정하는 방식
• 이전에 다른 숫자를 통해 사이클이 발견됐어도 그냥 넘어가기 때문에 중복으로 탐색하게 된다

말하자면 1 -> 3 <-> 3 으로 1에서 시작해도 3이라는 사이클을 발견할 수 있는데, 반드시 사이클에 포함되는 숫자인 3에서 시작할 경우에만 사이클을 찾은 걸로 인정한다는 것이다

# 텀 프로젝트

def dfs(node, visited):
    if visited[node]:
        return [0]
    visited[node] = 1

    return dfs(graph[node], visited) + [node]

for tc in range(int(input())):
    n = int(input())
    graph = [0] + list(map(int, input().split()))
    visited = [0]*(n+1)

    for i in range(1, n+1):
        if not visited[i]:
            visit = dfs(graph[i], visited[:])
            # print(i, visit)
            if visit[1:2] == [i]:
                for v in visit[1:]:
                    visited[v] = 1

    print(n-sum(visited))

풀이2

• 이미 한 번 방문한 곳은 재방문하지 않도록 어떤 시작 숫자에서 시작됐건 사이클이 발견되면 탐색을 종료하고 그 탐색 순서에서 사이클에 포함되지 않은 숫자의 개수만 세는 방식
• 1에서 탐색을 시작하게 되면, 5, 2, 3, 4를 차례대로 발견하게 되고, 4 -> 5에서는 5에 이미 방문처리가 되어 있기 때문에 5에서 종료
• 현재 탐색의 시작이 되는 1에서부터 위에서 마지막으로 탐색이 종료되었던 숫자까지의 개수를 카운트한다. 만일 사이클을 이룬다면 그림처럼 1에서 시작해 5에서 바로 종료될 수 있을 것

# 텀 프로젝트

for tc in range(int(input())):
    N = int(input())
    graph = [0] + list(map(int, input().split()))
    visited = [0] * (N+1)

    check = 0
    for idx in range(1, N+1):
        if visited[idx]:
            continue

        # 이미 방문된 곳이 있다면 탐색 종료
        cur = idx
        while not visited[cur]:
            visited[cur] = idx
            cur = graph[cur]
        
        # 이 탐색의 시작 숫자 ~ 사이클의 시작 숫자 사이의 개수 세기
        # 만약 시작 숫자 = 사이클의 시작 숫자라면 0개가 된다
        next = idx
        while next != cur:
            check += 1
            next = graph[next]
        
    print(check)