종이접기( BOJ 20187 )

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

20187번: 종이접기

 

문제 파악하기

2^N*2^N 크기의 종이를 접은 다음 모서리 부근에 구멍을 하나 뚫었을 때, 구멍이 뚫리는 모든 위치를 출력하는 문제입니다. 항상 가로, 세로 각각 K번씩 접는다고 명시했기 때문에 종료 조건을 따로 설정할 필요가 없으며, 예외 사항을 생각하지 않아도 됩니다. 이 문제는 현재 종이의 모습을 적절하게 추상화한 다음, 종이가 접힌 역순으로 시뮬레이션하면 문제를 해결할 수 있습니다.

 

문제 해결하기

우선, 종이의 모습을 추상화하는 방법에 대해 생각해봅시다. 종이는 현재 상하좌우 중 한 가지 방향으로 접혀서 1/2 크기로 점점 줄어들고 있습니다. 그리고 마지막에는 1*1크기의 사각형으로 접힙니다. 따라서, 우리는 종이를 1*1크기의 사각형으로 모두 나눈 다음, 현재 보여지는 종이의 가로, 세로 범위를 표시하면 점점 접혀지는 종이의 모습을 표현할 수 있습니다.

>> void sv(int idx, int i1, int i2, int j1, int j2) { } // i1, i2: 현재 종이의 세로 범위 / j1, j2: 현재 종이의 가로 범위

 

이렇게 함수로 종이의 모습을 추상화하면 남은 작업은 시뮬레이션입니다. 이 문제에서 시뮬레이션은 종이에 구멍을 뚫은 다음, 종이를 펼치면서 뚫린 위치를 확인하는 과정이라고 생각하면 됩니다. 여기서 중요한 점은 접혔던 종이를 펼치면 구멍이 뚫린 위치는 항상 대칭된다는 걸 잊으면 안됩니다. 위/아래로 접은 경우에는 밑변 혹은 윗변을 기준으로 대칭되는 위치에 구멍이 생기며, 왼쪽/오른쪽으로 접은 경우에는 옆면을 기준으로 대칭되는 위치에 구멍이 생깁니다. 이 점에 유의하면 각각의 종이에 뚫린 구멍은 손쉽게 찾을 수 있습니다.

 

시뮬레이션을 돌릴 때에는 과정이 진행되는 순서가 중요합니다. 종이를 접은 후, 하나씩 펼치면서 구멍을 확인하기 위해서는 가장 먼저 해야할 작업은 무엇일까요? 바로 종이를 접는 과정입니다. 따라서, 우리는 먼저 종이를 접은 다음, 펼치면서 구멍이 뚫린 위치를 확인하면서 뚫려야 하는 위치를 하나씩 찾으면 결국 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#define NMAX 10
using namespace std;
 
int N, H;
char c;
 
vector< char > inp;
int maps[1<<NMAX][1<<NMAX];
 
// 대칭값으로 변환
int convert(int val, int k) {
    if(k == 0) {
        switch(val) {
            case 0: return 2;
            case 1: return 3;
            case 2: return 0;
            default: return 1;
        }
    }
 
    else {
        switch(val) {
            case 0: return 1;
            case 1: return 0;
            case 2: return  3;
            default: return 2;
        }
    }
}
 
 
void sv(int idx, int i1, int i2, int j1, int j2) {
    if(idx == N*2) maps[i1][j1] = H;
    else {
        if(inp[idx] == 'U') {
            sv(idx+1, i1, (i1+i2)/2, j1, j2);
 
            for(int i=(i1+i2)/2+1;i<=i2;i++) {
                for(int j=j1;j<=j2;j++) {
                    maps[i][j] = convert(maps[(i1+i2) - i][j], 0);
                }
            }
        }
 
        else if(inp[idx] == 'D') {
            sv(idx+1, (i1+i2)/2+1, i2, j1, j2);
 
            for(int i=i1;i<=(i1+i2)/2;i++) {
                for(int j=j1;j<=j2;j++) {
                    maps[i][j] = convert(maps[(i1+i2) - i][j], 0);
                }
            }
        }
 
        else if(inp[idx] == 'R') {
            sv(idx+1, i1, i2, (j1+j2)/2+1, j2);
 
            for(int i=i1;i <=i2;i++) {
                for(int j=j1;j<=(j1+j2)/2;j++) {
                    maps[i][j] = convert(maps[i][(j1+j2) - j], 1);
                }
            }
        }
 
        else {
            sv(idx+1, i1, i2, j1, (j1+j2)/2);
 
            for(int i=i1;i<=i2;i++) {
                for(int j=(j1+j2)/2+1;j<=j2;j++) {
                    maps[i][j] = convert(maps[i][(j1+j2) - j], 1);
                }
            }
        }
    }
}
 
int main() {
    // 입력
    scanf("%d\n", &N);
    for(int i=0;i<N*2;i++) {
        scanf("%c ", &c);
        inp.push_back(c);
    }
    scanf("%d", &H);
 
    // solve
    sv(0, 1, 1<<N, 1, 1<<N);
    
    // 출력
    for(int i=1;i<=(1<<N);i++,puts(""))
        for(int j=1;j<=(1<<N);j++) printf("%d ", maps[i][j]);
        
}

후기

종이를 접는 문제는 항상 까다롭다는 생각이 듭니다. 하지만, 종이의 모습을 추상화하는 방법만 떠올릴 수 있다면 그리 난이도가 있는 문제라고 생각하지 않습니다. 재귀함수를 막 배우고 활용법을 연습하는 사람에게 추천할만한 문제라고 생각합니다.