체스판( BOJ 12960 )

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

12960번: 체스판

 

문제 파악하기

체스판 위에 놓을 수 있는 L-모양 타일의 최대 개수를 찾는 문제입니다. 단순히 놓는 것이 아닌, 몇 가지 규칙이 있는데 그 중 가장 중요한 규칙은 다음 2가지 입니다. 우선, 'X' 표시에는 이미 체스말이 놓여있기 때문에 L-모양 타일을 놓을 수 없습니다. 그리고 타일의 꼭지점 칸(두 정사각형과 붙어있는 칸)은 항상 체스판의 검은 칸 위에 놓아야 합니다. 이 2가지 조건만 기억한다면 문제를 푸는데 무리가 없을 듯 합니다.

 

문제 해결하기

문제를 유심히 보면 L-모양 타일은 항상 현재 열과 다음 열에만 영향을 미친다는 점을 파악할 수 있습니다. 따라서 이 문제는 한 열씩 채워보면서 최대한 타일을 많이 놓다보면 전체 체스판에 타일을 최대한 놓을 수 있게 됩니다. 이렇게 큰 문제를 작은 문제로 분할할 수 있을 때, 다이나믹 프로그래밍 기법을 사용할 수 있습니다. 그럼 우리가 탐색을 할 때, 알고 있어야 할 요소들을 생각해봅시다. 우선, 현재 탐색하는 체스판의 위치(idx)는 알고 있어야 합니다. 그래야 마지막에 탐색이 종료되었는지 알 수 있습니다. 그리고, 현재 위치를 기준으로 총 (R+1)개 칸의 상태(check) 또한 필요합니다. 이전에 놓은 타일이 현재 위치에서 타일을 놓을 때 영향을 미칠 수 있기 때문입니다. 그리고 (R+1)개의 칸만 필요한 이유는 이전에 놓은 타일이 현재 위치 기준으로 R번째 위치까지 영향을 미치기 때문입니다. 그렇다면 우리는 필요한 요소를 가지고 다음과 같이 dp배열을 선언할 수 있습니다.

 

dp[idx][check] = (idx)번 위치에서 (check)상태를 가지고 있을 때, 앞으로 놓을 수 있는 타일의 최대 개수

 

이렇게 dp배열을 선언하고, L-모양 타일을 놓으면서 check의 상태를 변경시켜주면 우리는 원하는 결괏값을 구할 수 있습니다. 여기서 중요한 점은 현재 위치가 검은 칸인지, 하얀 칸인지에 따라 놓을 수 있는 타일의 모양이 다르다는 것입니다. 놓는 모양에 따라 check 배열이 달라지기 때문에 이 점만 유의하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define RMAX 5
#define CMAX 50
using namespace std;
 
int R, C;
char inp[RMAX][CMAX];
 
int dp[RMAX*CMAX][1<<RMAX];
 
bool safe(int r, int c) {
    if(r<0 or c<0 or r>=R or c>=C) return 0;
    else return 1;
}
 
bool isSet(int r, int c, int check, int n) {
    if(!safe(r, c)) return 1;
    else {
        if(inp[r][c] == 'X') return 1;
        else return check & (1<<n);
    }
}
 
int sv(int idx, int check) {
    if(dp[idx][check] >= 0) return dp[idx][check];
    else if(idx == R*C) return dp[idx][check] = 0;
    else {
        int r, c, ret;
 
        // init
        r = idx%R; c = idx/R;
        ret = sv(idx+1, check>>1);
 
        // 현재 위치에 블럭을 놓을 수 있는 경우
        if(!isSet(r, c, check, 0)) {
 
            // 검정 칸인 경우
            if((r+c)%2 == 0) {
                if(!isSet(r+1, c, check, 1) and !isSet(r, c+1, check, R)) {
                    ret = max( ret, sv(idx+1, (check>>1)+1+(1<<(R-1)))+1 ) ;
                }
            }
 
            // 하얀 칸인 경우
            else {
                if(!isSet(r+1, c, check, 1) and !isSet(r+1, c+1, check, R+1)) {
                    ret = max( ret , sv(idx+1, (check>>1)+1+(1<<R))+1 );
                }
 
                if(!isSet(r, c+1, check, R) and !isSet(r+1, c+1, check, R+1)) {
                    ret = max( ret, sv(idx+1, (check>>1)+(1<<(R-1))+(1<<R))+1 );
                }
 
                if(!isSet(r-1, c+1, check, R-1) and !isSet(r, c+1, check, R)) {
                    ret = max( ret, sv(idx+1, (check>>1)+(1<<(R-2))+(1<<(R-1)))+1 );
                }
            }
        }
 
        return dp[idx][check] = ret;
    }
}
 
int main() {
    // input
    scanf("%d %d", &R, &C);
    for(int i=0;i<R;i++) scanf("%s", inp[i]);
 
    // DP
    memset(dp, -1, sizeof(dp));
    printf("%d", sv(0, 0));
}
/*
2 3
...
...
ans: 2
*/

이렇게 현재 위치를 기준으로 다음 위치들의 상태를 스크롤링 하듯이 저장하는 기법을 비트 스크롤링 기법이라고 합니다. 이 문제는 비트 스크롤링 기법을 연습하는 사람에게 추천하고 싶은 문제입니다.