[백준] 9466번 텀 프로젝트, dfs, 반복 순열

문제

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

나의 풀이

dfs를 잘 사용해야 하는 문제. 주어진 리스트에서 반복 순열을 구성하는 원소들의 개수를 구하는 문제이다.
(실제 구해야 하는 답은 전체 원소 개수 - 반복순열을 구성하는 원소의 개수)

이 문제의 핵심은 dfs 에서 반복 순열을 구하는 것이다.
예를 들어, dfs 가 1 -> 3 -> 4 -> 6 -> 7 -> 4 로 구성될 때, [4, 6, 7] 이 반복순열을 구성한다.
이 값들의 개수를 구하기 위해서 dfs 함수 내에 cycle이라는 리스트를 활용하였다.
dfs를 호출할 때마다 cycle에 원소들을 넣어주고, next 값이 cycle에 존재할 때 그 값이 반복순열을 이루는 첫번째 값을 의미한다. next 값부터 그 뒤 모든 값까지의 길이를 ans에 더해주면 된다.

이 문제에서 또 주의할 점은 recusionlimit을 굉장히 큰 값으로 지정해야 한다는 점이다.

나의 첫 번째 풀이 by DFS

import sys

sys.setrecursionlimit(1000000)
T = int(sys.stdin.readline())

def dfs(cycle, n):
    global visited, students_list, ans
    visited[n] = 1
    cycle.append(n)
    nxt = students_list[n]

    if visited[nxt] != 0: # next에 이미 방문한 경우
        if nxt in cycle:  # cycle안에 next 값이 존재 -> cycle 내 반복순열이 존재
            ans += len(cycle[cycle.index(nxt):]) # next 값부터 그 뒤 모든 값(반복순열)의 길이만큼 ans에 더함
            return
    else:
        dfs(cycle, nxt)

for _ in range(T):
    students_num = int(sys.stdin.readline())
    input_students = list(map(int, sys.stdin.readline().split()))

    students_list = [0] + input_students

    visited = [0] * (students_num + 1)
    ans = 0
    for j in range(1, students_num+1):
        if visited[j] == 0:
            cyc_list = []
            dfs(cyc_list, j)
    print(students_num - ans)

나의 두 번째 풀이 by BFS

import sys

sys.setrecursionlimit(1000000)
T = int(sys.stdin.readline())

for _ in range(T):
    students_num = int(sys.stdin.readline())
    input_students = list(map(int, sys.stdin.readline().split()))

    students_list = [0] + input_students
    visited = [0] * (students_num + 1)
    ans = 0

    for j in range(1, students_num+1):
        if visited[j] == 0:
            cyc_list = []
         
            # Solved by BFS
            queue = []
            queue.append(j)
            visited[j] = 1
            cyc_list.append(j)

            while queue:
                p = queue.pop(0)
                if visited[students_list[p]] == 1:
                    if students_list[p] in cyc_list:
                        ans += len(cyc_list[cyc_list.index(students_list[p]):])
                        break
                else:
                    visited[students_list[p]] = 1
                    queue.append(students_list[p])
                    cyc_list.append(students_list[p])
    print(students_num - ans)