[백준] 10451번 - 순열 사이클

문제 링크 : https://www.acmicpc.net/problem/10451

문제 탐색하기

1) 문제 분석

순열 사이클이란?: 순열에서 특정 숫자를 따라가다가 다시 원래 숫자로 돌아오면 그것을 하나의 사이클로 본다.
문제 목표
: 주어진 순열에서 이러한 순열 사이클의 총 개수를 구하면 된다.
접근 방법
: 마치 그래프 탐색 문제처럼, 방문하지 않은 숫자에서 시작해 사이클을 찾을 때마다 1개 카운트하고, 모든 숫자를 방문할 때까지 이를 반복하면 된다.

2) 가능한 시간복잡도

(1) 입력 처리

첫 줄에서 테스트 케이스 개수 T를 입력받고, 각 테스트 케이스마다 순열 크기 N과 순열 배열을 입력받는다.
입력 데이터는 최대 2,000줄 (1,000개의 순열 × 2줄)을 처리해야 하며, 각 줄은 공백으로 구분된 숫자 형태.
숫자 변환 및 배열로 저장하는 작업은 O(N) 소요된다.
T개의 테스트 케이스가 있으므로 -> O(T × N)

(2) 순열 사이클 탐색 및 계산

각 테스트 케이스에서 순열을 한 번씩 순회하며 사이클을 구함.
사이클을 구하는 과정에서 각 노드는 최대 한 번만 방문됨. 즉, N개의 노드에 대해 while문이 전체적으로 최대 N번 실행됨.
1번 노드부터 N번 노드까지 순회하는 for문과 while문이 중첩처럼 보이지만, 실제로는 모든 노드를 최대 한 번씩만 방문하므로: -> O(N)

(3) 출력 처리

각 테스트 케이스마다 결과를 출력.
출력은 T번 수행되며, 각 결과 출력은 O(1)이므로: -> O(T)

(4) 총 시간복잡도

입력 처리 : O(T × N)
사이클 계산 : O(T × N)
출력 처리 : O(T)
총합 : O(T × N)
(여기서 T는 테스트 케이스 개수, N은 순열 크기)

3) 알고리즘 선택 이유

이 문제는 순열을 단순 배열이 아닌 그래프 형태로 추상화하고, 각 노드를 따라가면서 사이클을 찾는 탐색 문제로 해석할 수 있다. 그래서 다음과 같은 이유로 해당 알고리즘을 선택했다:

각 숫자는 하나의 노드이며, 자신이 가리키는 숫자로 간선이 연결된 단방향 그래프 형태를 이룬다.
이 그래프에서 사이클 개수를 찾는 문제로 해석 가능하다.
방문하지 않은 노드를 따라가며 탐색하다가 처음 노드로 되돌아오면 하나의 사이클이 완성된다.
방문 배열을 활용해 중복 탐색을 방지하고, 모든 노드를 최대 한 번씩만 방문하는 최적의 방식이다.

결과적으로, 완전탐색 + 방문 처리 방식이 가장 직관적이며 효율적이라 판단했다.

→ 입력 크기 (N ≤ 1,000)가 충분히 작기 때문에 O(N) 알고리즘으로도 모든 테스트 케이스를 충분히 빠르게 처리할 수 있다.

코드 설계하기

1. 실행 구조

1) 입력 처리

테스트 케이스 개수와 순열 배열들을 파싱

2) 사이클 탐색 함수

방문하지 않은 노드에서 시작
다음 노드를 따라가며 방문 처리
다시 시작 노드로 돌아오면 사이클 하나 완성

3) 사이클 개수 카운트 후 출력

2. 고민이 되었던 부분

순열 자체를 그래프처럼 생각하는 것이 익숙하지 않아서 처음엔 단순 배열 문제로만 생각했었다.
하지만 문제를 풀다보니 각 숫자가 하나의 노드로 작동하고 있다는 것을 깨닫게 되었고, 그래프의 사이클 개수를 찾는 문제로 전환해서 해결할 수 있었다.
이 문제에서 중요한 것은:
- 숫자마다 방문 처리를 확실히 해주는 것
- 숫자를 계속 따라가다가 다시 시작 지점으로 돌아오는 순간 사이클로 판단하는 것

정답 코드

JavaScript

// 사용 언어 : Javascript

// 입력 데이터 읽기 및 전처리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const repeatCount = Number(input[0]);   // 테스트 케이스 개수
const testCases = [];                   // 각 테스트 케이스 저장용

// 테스트 케이스 데이터 분리
let idx = 1;
for (let i = 0; i < repeatCount; i++) {
    const arrCount = Number(input[idx]);                               // 순열의 크기 N
    const arr = input[idx + 1].trim().split(' ').map(Number);          // 순열 배열
    testCases.push([arrCount, arr]);                                   // [N, 순열배열] 형태로 저장
    idx += 2;
}


// 순열 사이클 개수 구하는 함수
function getCicleCounts(arrCount, originArr) {
    let cicleCount = 0;                                // 순열 사이클 개수 카운트
    const visited = new Array(arrCount + 1).fill(false);  // 방문 체크 배열 (1-based index)

    // 1번 노드부터 N번 노드까지 순회
    for (let i = 1; i <= arrCount; i++) {
        if (!visited[i]) {                 // 아직 방문하지 않은 노드면 사이클 시작
            let current = i;

            // 해당 사이클을 따라가며 방문 처리
            while (!visited[current]) {
                visited[current] = true;                    // 현재 노드 방문 체크
                current = originArr[current - 1];           // 다음 노드로 이동 (0-based 인덱스 주의)
            }

            cicleCount++;   // 사이클 하나 완성됨 → 개수 증가
        }
    }

    return cicleCount;    // 순열 사이클 개수 반환
}


// 각 테스트 케이스 처리 후 출력
testCases.forEach(([arrCount, originArr]) => {
    console.log(getCicleCounts(arrCount, originArr));    // 각 케이스 결과 출력
});

마무리하며

이번 문제는 순열을 단순 배열로만 보지 않고 그래프처럼 추상화해서 생각하는 것이 핵심이었다. 처음엔 어떻게 사이클을 탐색해야 하는지 막막했지만, 순열을 노드로 보고 사이클을 따라가면서 방문 처리하는 방식으로 해결할 수 있었다.

코드로 구현하는 과정에서 중요했던 부분은:

방문 체크 배열을 적절히 활용해 중복 탐색을 막는 것
while문을 통해 간결하게 사이클을 추적하는 것

문제를 빨리 풀기보다는, 문제 자체를 올바르게 이해하고 왜 이렇게 풀어야 하는지를 고민하는 태도가 얼마나 중요한지 다시 한번 느꼈다. 앞으로도 ‘정답’보다 ‘문제 접근법과 해결 과정’을 더 중요하게 여기는 개발자가 되고 싶다.

최근 글