Swapity Swapity Swap( BOJ 18783 )

문제 : https://www.acmicpc.net/problem/18783

18783번: Swapity Swapity Swap

 

문제 파악하기

모든 운동이 끝났을 때, N마리 소들의 배치를 출력하는 문제입니다. 소들은 M개의 세트로 이루어진 운동을 총 K번 반복하며, 한번 동작을 할 때마다 정해진 범위 안의 소들의 위치가 반전됩니다. 문제에서 요구하는 K의 값이 최대 10억이기 때문에 모든 경우를 탐색하는 브루트포스보다는 효율적인 알고리즘이 필요하다는 걸 확인할 수 있습니다.

 

문제 분석하기

그렇다면 어떤 알고리즘을 활용할 수 있을까요? 우선 모든 운동은 항상 M개의 세트를 모두 마친다고 했습니다. 따라서 1번의 운동(M번의 세트)가 모두 끝난 다음, 각각의 소가 어떤 자리로 이동하는지 알 수 있다면 M번의 세트를 모두 진행하지 않아도 다음 운동 후 모든 소의 위치를 구할 수 있습니다. 예를 들어 1번 소가 1번의 운동이 끝난 다음 5번 자리로 이동했으며, 현재 1번 자리에는 2번 소가 있다고 가정해보겠습니다. 이 상태에서 1번의 운동을 추가로 한다면 우리는 직접 M번의 세트를 할 필요 없이 2번 소가 5번 자리로 이동할 것이라는 걸 알 수 있습니다. 이처럼 운동이 끝난 후에 이동할 다음 위치를 배열을 사용하여 저장한다면 좀 더 빠르게 결과를 탐색할 수 있습니다.

 

하지만 배열을 사용한다고 해서 알고리즘이 충분히 빨라지지는 않습니다. 아무리 M번의 세트를 생략하더라도 우리는 최대 10억 번의 운동을 한 다음 결과를 출력할 수 있어야 하기 때문입니다. 여기서 우리가 사용할 수 있는 자료구조는 바로 희소 테이블입니다. 희소 테이블은 말 그대로 값이 적다는 걸 의미하며, 공간에 비해 작은 값만을 저장하는 테이블을 의미합니다. 희소 테이블은 지금과 같이 동일한 작업이 반복되는 경우에 주로 사용합니다. 희소 테이블에서 각각의 행은 (2^i)번째 작업 후의 결과를 의미하며, 희소 테이블에 저장된 값을 적절하게 사용하면 O(logN)만에 결과를 도출할 수 있습니다.

 

그럼 희소 테이블을 먼저 만들어보겠습니다. 희소 테이블에서 행은 (2^i)번째 작업의 결과를 의미하며, 이 값은 이전 행의 값을 통해 찾을 수 있습니다. 만약 우리가 구하고자 하는 위치의 이전 값이 t라면 우리는 현재 위치에서 총 2^(i-1)번의 작업을 한다면 t번째 위치로 이동한다는 점을 파악할 수 있습니다. 그렇다면 이 상태에서 한번 더 2^(i-1)번의 작업을 하면 어떨까요? 그렇다면 결괏값은 t번째 위치에서 2^(i-1)번 작업한 횟수를 의미하며, 결국 우리는 현재 위치에서 (2^i)번의 작업을 한 결과는 이전 행에서 t번째 위치의 값이라는 결론을 도출할 수 있습니다.

 

sparse[i][j] = sparse[ sparse[i][j-1] ][j-1]

 

이처럼 희소 테이블은 이전의 결괏값을 통해 현재 결괏값을 구할 수 있으며, 2의 거듭제곱 횟수만을 기록하기에 훨씬 효율적으로 정보를 저장할 수 있습니다. 이렇게 희소 테이블을 제작했다면 남은 일은 K번째 작업의 결괏값을 구하는 일입니다. K번째 작업의 결괏값을 구하는 과정은 희소 테이블의 속성을 떠올려보면 어렵지 않게 구할 수 있습니다. 희소 테이블은 항상 2의 거듭제곱 횟수만큼 반복합니다. 따라서, K번째 결괏값을 구하기 위해서는 K를 2의 거듭제곱의 합으로 바꾸면 되며, 보통 2진수 변환에서 사용한 알고리즘을 활용하면 쉽게 구할 수 있습니다.

 

다만, 놓치지 말아야 할 점은 희소 테이블에 초깃값입니다. 단순히 1번의 운동이 끝난 후의 결괏값을 저장하는 것이 아닌, 1번의 움직임이 끝난 후 어떤 위치로 이동하는지를 저장해야 합니다. 입력 예시를 통해 살펴보면, 첫 번째 운동이 끝난 후의 결괏값은 [ 1, 5, 7, 6, 2, 3, 4 ] 가 됩니다. 여기서 우리가 저장할 값은 각각의 소가 어떤 위치로 움직였는지이며, [ 1, 5, 6, 7, 2, 4, 3 ] 의 값을 저장해야 합니다. 이 값을 토대로 희소 테이블을 만든 다음, K번 운동 후의 결괏값을 구하면 우리가 원하는 정답을 구할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#import <stdio.h>
#define NMAX 100010
#define MMAX 32
#define SWAP(a, b) (a=a^b, b=a^b, a=a^b)
using namespace std;
 
int N, M, K;
int l, r;
 
int inp[NMAX], cur[NMAX], bef[NMAX];
int convert[NMAX];
int query[NMAX][MMAX];
 
int main() {
    scanf("%d %d %d", &N, &M, &K);
    for(int i=1;i<=N;i++) inp[i] = cur[i] = bef[i] = i;
    
    for(int i=1;i<=M;i++) {
        scanf("%d %d", &l, &r);
        
        while(l<r) {
            SWAP(inp[l], inp[r]);
            l++; r--;
        }
    }
    
    for(int i=1;i<=N;i++) query[inp[i]][0] = convert[inp[i]] = i;
    
    // 희소테이블 작성
    for(int j=1;j<MMAX;j++) {
        for(int i=1;i<=N;i++) {
            query[i][j] = query[query[i][j-1]][j-1];
        }
    }
    
    // K번 쿼리 반복하기
    for(int j=0;K>0;j++,K/=2) {
        if(K%2 == 0) continue;
        
        for(int i=1;i<=N;i++) cur[query[i][j]] = bef[i];
        
        for(int i=1;i<=N;i++) bef[i] = cur[i];
    }
    
    
    // 출력
    for(int i=1;i<=N;i++) printf("%d\n", cur[i]);
}
 

후기

희소 테이블을 연습할 수 있는 좋은 문제입니다. 희소 테이블은 추후에 최소 공통 조상(LCA)와 같은 알고리즘에서 자주 사용되기에 기억할 필요가 있습니다.