[순열 사이클 분할] 백준 10451 순열 사이클

이번 포스트에서는 백준 10451번 문제인 "순열 사이클"을 파이썬으로 풀이한 방법을 공유하고자 합니다. 이 문제는 주어진 순열 내에서 사이클이 몇 개 존재하는지를 찾는 문제로, DFS(깊이 우선 탐색)를 활용하여 해결할 수 있습니다.

순열 사이클 분할 설명

순열 사이클 분할은 주어진 순열을 사이클 구조로 분해하는 과정입니다. 순열은 각 요소가 다른 요소로 매핑되는 일종의 함수입니다. 이때, 순환 구조(사이클)를 찾는다는 것은 해당 순열 내에서 자기 자신으로 돌아오는 경로를 찾는 것을 의미합니다.

예를 들어, 순열이 다음과 같이 주어졌다고 가정합니다:

• ( \text{순열} = [2, 3, 1, 5, 6, 4] )

이 순열에서 사이클을 찾아보면:

• 1 → 2 → 3 → 1 (사이클 형성)
• 4 → 5 → 6 → 4 (사이클 형성)

따라서, 이 순열은 두 개의 사이클로 분할할 수 있습니다: ( (1, 2, 3) ) 그리고 ( (4, 5, 6) ).

순열 사이클 분할 알고리즘

순열 사이클을 찾기 위한 알고리즘은 보통 DFS(깊이 우선 탐색) 또는 단순한 탐색 알고리즘을 사용하여 구현할 수 있습니다.
아래는 문제를 해결하기 위한 코드입니다:

count = 0

def check_permutation_cycle(dict_value, current_node, visited):
    if visited[current_node]:
        return 1

    visited[current_node] = True
    return check_permutation_cycle(dict_value, dict_value[current_node], visited)


T = int(input())
for _ in range(T):
    N = int(input())
    count = 0
    dict_value = {}
    keys = list(map(int, input().split()))
    visited = [False] * (N + 1)
    for value in range(1, N + 1):
        dict_value[value] = keys[value - 1]
    for current_node in range(1, N + 1):
        if not visited[current_node]:
            count += check_permutation_cycle(dict_value, current_node, visited)

    print(count)

이 코드에서는, 주어진 순열을 딕셔너리로 변환하고, 각 노드를 순회하며 DFS를 사용하여 순열 사이클을 찾아냅니다. 각 사이클을 찾을 때마다 카운트를 증가시켜 최종적으로 순열 사이클의 개수를 출력합니다.

코드 설명

1. check_permutation_cycle 함수: 이 함수는 DFS를 사용하여 순열에서 사이클을 찾습니다. 현재 노드를 방문했다고 표시하고, 다음 노드로 이동하여 방문을 반복합니다. 이미 방문한 노드에 도달하면 사이클이 존재함을 의미합니다.
2. 입력 처리: 주어진 순열을 딕셔너리로 변환하여 각 노드의 다음 노드를 쉽게 조회할 수 있게 했습니다.
3. 사이클 탐색: 각 노드를 방문하지 않았다면 DFS를 통해 사이클을 찾고, 그 개수를 카운트합니다.

결론

이 문제는 DFS를 활용하여 해결할 수 있는 전형적인 그래프 탐색 문제입니다. 파이썬의 딕셔너리를 이용해 순열을 효과적으로 관리하고, DFS를 사용하여 사이클을 찾아내는 방식으로 문제를 해결할 수 있습니다. 이 방법은 시간복잡도가 O(N)으로 매우 효율적입니다.