[백준/C] (G5) Swaps - 13214

Baekjoon Online Judge의 13214번 Swaps  문제의 C풀이입니다.

13214번: Swaps

🧠문제 분석

두 개의 배열 A와 B가 있으며, 각각 1부터 N까지의 숫자를 포함하지만 반드시 이 순서대로는 아닙니다. 배열 A의 원소를 서로 바꾸는 연산을 통해 배열 A를 배열 B와 동일하게 만들 수 있습니다. 목표는 배열 A를 배열 B로 변환하는데 필요한 최소 연산 횟수를 찾는 것입니다.

입력
첫 번째 줄에는 배열 A와 B의 크기를 나타내는 정수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)
두 번째 줄에는 배열 A의 요소가 공백으로 구분되어 주어집니다.
세 번째 줄에는 배열 B의 요소가 공백으로 구분되어 주어집니다.
출력
배열 A를 배열 B로 변환하는 데 필요한 최소 연산 횟수를 출력합니다.

🤔문제 풀이

위치 매핑 생성: 배열 B에서 각 요소의 위치를 매핑합니다. 이를 위해 pos 배열을 사용하여 배열 B의 각 요소가 위치한 인덱스를 저장합니다.

방문 배열 초기화: 원소가 순환 구조를 형성하는지 추적하기 위해 visited 배열을 사용합니다. 모든 원소는 초기에 방문하지 않은 상태(0)로 설정됩니다.

순환 구조 찾기: 배열 A를 순회하면서 순환 구조를 찾습니다. 각 순환 구조는 한 번의 연산으로 내부의 원소를 올바른 위치로 이동시킬 수 있습니다. 순환 구조의 크기가 k일 때, 필요한 최소 연산 횟수는 k−1입니다.

총 연산 횟수 계산: 각 순환 구조에 대해 필요한 연산 횟수를 누적하여 총 연산 횟수를 계산합니다.

이 알고리즘은 순환 구조를 찾아서 각 순환 구조 내에서 필요한 최소한의 교환 횟수를 계산함으로써 전체 배열을 올바른 순서로 바꾸는 데 필요한 최소 연산 횟수를 효율적으로 찾습니다.

💻코드

#include <stdio.h>
#include <stdlib.h>

// 최소 교환 횟수를 계산하는 함수
int minSwaps(int *A, int *B, int N) {
    int pos[N+1], visited[N], i, j, ans = 0;

    // 배열 B에서 각 원소의 인덱스를 매핑합니다.
    for (i = 0; i < N; i++) {
        pos[B[i]] = i;
    }

    // visited 배열을 초기화합니다. (방문하지 않음으로 설정)
    for (i = 0; i < N; i++) {
        visited[i] = 0;
    }

    // 순환 구조를 찾아 교환 횟수를 계산합니다.
    for (i = 0; i < N; i++) {
        if (visited[i] || pos[A[i]] == i)
            continue; // 이미 방문했거나 이미 올바른 위치에 있는 경우

        int cycle_size = 0;
        j = i;

        // 순환 구조를 찾습니다.
        while (!visited[j]) {
            visited[j] = 1; // 방문 표시
            j = pos[A[j]];  // 다음 원소로 이동
            cycle_size++;
        }

        // 순환 구조 내에서의 교환 횟수를 더합니다.
        if (cycle_size > 0) {
            ans += (cycle_size - 1);
        }
    }

    return ans; // 총 교환 횟수 반환
}

int main() {
    int N;
    scanf("%d", &N); // 배열의 크기 N을 입력받습니다.

    int A[N], B[N], i;
    // 배열 A의 원소를 입력받습니다.
    for (i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    // 배열 B의 원소를 입력받습니다.
    for (i = 0; i < N; i++) {
        scanf("%d", &B[i]);
    }

    // 최소 교환 횟수를 계산하여 출력합니다.
    printf("%d\n", minSwaps(A, B, N));

    return 0;
}