[백준] 10451 - 순열 사이클 (python 파이썬)

백준 문제 바로가기

"""수도코드
1. 입력받기: 테스트 케이스 개수 t, 순열의 크기 n, 순열을 저장하는 리스트 arr
2. 각 노드가 노드를 따라가서 방문하는것이고 순환을 돌 수 있기에 방문 체크를 해줘야 하므로 visited도 만들어준다,
3. 함수정의
3.1 매개변수로 들어온 노드 v는 방문한걸로 체크해준다.
3.2 그 다음으로 갈 노드를 v를 통해 가져온다.
3.3 다음 노드인 next로 갈 수 있다면 재귀를 통해 이동해준다.
"""


def solution(v):
    visited[v] = 1
    next = arr[v]
    if visited[next] == 0:
        solution(next)
    return


t = int(input())
arr = [0]
for _ in range(t):
    cnt = 0
    n = int(input())
    visited = [0] * (n + 1)
    arr = list(map(int, input().split()))
    # arr = [0] + list(map(int, input().split()))
    arr.insert(0, 0)
    for i in range(1, n + 1):
        if visited[i] == 0:
            solution(i)
            cnt += 1
    print(cnt)

간단한 dfs/bfs방식으로 푸는 문제다. 나는 우선 dfs로 풀었다. arr에 입력 리스트를 받아서 넣어주고 맨 앞에 0을 넣어줬는데 arr = [0] + list(map(int, input().split())) 이렇게도 표현해서 받을 수 있다는 점!!

함수안에서는 노드를 방문체크해주고 다음으로 갈 노드를 가져와서 방문했는지 확인해서 재귀를 통해 이동하면 된다.