[Algorithm][Python] 백준(BOJ) 10451 순열 사이클

[문제]

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

---

[내 코드]

import sys

def dfs(v):
    visited[v] = True
    next = numbers[v] # 다음 방문
    if not visited[next]: #방문하지 않았다면
        dfs(next)

for _ in range(int(input())):
    n = int(sys.stdin.readline())

    cycle = 0
    visited = [False] * (n+1)

    numbers = [0] + list(map(int, sys.stdin.readline().strip().split()))

    for i in range(1, n+1):
        if not visited[i]: # 방문하지 않았다면
            dfs(i)
            cycle += 1
    
    print(cycle)

💡문제 풀이

주어진 수에 이어 끝까지 확인을 하는 것이므로 DFS(깊이 우선 탐색)를 통해 해결할 수 있다.

1. 방문 여부를 확인하는 리스트를 만든다.
2. 인덱스에 맞게 입력된 리스트를 인덱스 1부터 저장한다.
3. 1부터 n(순열의 크기)까지 for문을 돌면서 해당 숫자의 목적지를 방문한다.

   3-1. 방문할 숫자의 다음 숫자를 방문하지 않았다면 dfs를 재귀호출하여 방문한다.
   3-2. 방문했다면, cycle 에 1을 더한다.

❌시도했으나 실패한 것

문제에서의 배열 [[1 2 3 4 5 6 7 8], [3 2 7 8 1 4 5 6]]처럼 2차원 리스트로 선언하여 구현하려 했으나 실패ㅠㅠ 왜 안되지..??