[알고스팟] 게임판 덮기

https://algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

 

 

재귀함수를 이용하여 문제를 풀었다.

게임판을 (0,0)부터 시작하는 좌표상에 위치시킨다고 할 때, L자 블록이 특정 위치 (tx,ty)를 포함하는 경우는 다음과 같이 총 12가지이다. 

 

 

(tx,ty)를 기준으로 했을 때 (tx,ty)를 포함시키는 L블럭이 감싸는 3개의 좌표 모두 흰 칸이어야만 L블럭을 사용할 수 있다. 즉, (tx,ty) (x1,y1) (x2,y2) 세 좌표 모두 흰 칸이어야 한다는 뜻이다. 또한, 이 세 좌표가 게임판의 범위를 넘어서면 안된다. 특정 좌표가 0보다 작다거나, 게임판 너머에 위치해 있으면 L블럭을 놓을 수 없다. 따라서 이러한 조건을 만족한 경우에만 블럭을 놓고, 그 다음 흰 칸으로 넘어간다.

 

 

(x1,y1) (x2,y2)는 (tx,ty)을 기준으로 잡아서 설정한다. 위의 각 12가지의 경우마다 (x1,y1) (x2,y2)가 어떻게 결정되는지는 3차원 배열을 통해 정하였다.

int x[3][4][2]={
    {{0,1},{0,1},{-1,0},{-1,0}},  // (1) (2) (3) (4)
    {{0,1},{-1,-1},{-1,0},{1,1}}, // (5) (6) (7) (8)
    {{-1,-1},{0,1},{1,1},{-1,0}}  // (9) (10) (11) (12)
};
int y[3][4][2]={
    {{-1,0},{1,0},{0,1},{0,-1}},  // (1) (2) (3) (4)
    {{1,1},{0,1},{-1,-1},{0,-1}}, // (5) (6) (7) (8)
    {{-1,0},{-1,-1},{0,1},{1,1}}  // (9) (10) (11) (12)
};

 

    for(int i=0;i<3;i++){
        for(int j=0;j<4;j++){
            int x1=tx+x[i][j][0];  // x1을 결정 
            int y1=ty+y[i][j][0];  // y1을 결정
            
            int x2=tx+x[i][j][1];  // x2를 결정
            int y2=ty+y[i][j][1];  // y2를 결정
            
            if(x1<0 || x1>=W || y1<0 || y1>=H || arr[y1][x1]==1) // 범위를 벗어나거나 흰칸이 아니면 안됨
                continue;
            
            if(x2<0 || x2>=W || y2<0 || y2>=H || arr[y2][x2]==1) // 범위를 벗어나거나 흰칸이 아니면 안됨
                continue;
            
            arr[ty][tx]=arr[y1][x1]=arr[y2][x2]=1; // L블럭으로 채우는 행위
          
            recursive(arr,index+1); // 그 다음 흰 칸으로 넘어간다(재귀)
        
            arr[ty][tx]=arr[y1][x1]=arr[y2][x2]=0;
        }
    }

 

arr배열의 값이 1이 된다는 것은 해당 위치가 블럭으로 덮이게 되어 검은칸이 되었다는 의미이며, 0이 된다는 것은 해당 위치가 흰 칸이라는 뜻이다. 만약 (tx,ty) (x1,y1) (x2,y2) 모두 L블럭으로 덮이게 되면 세 좌표 모두 검은칸이 되는 것이므로 

 

arr[ty][tx]=arr[y1][x1]=arr[y2][x2]=1; // L블럭으로 채우는 행위

 

L블럭으로 채우고, 다음 흰칸으로 넘어간다. 이런 방식으로 마지막까지 남은 흰 칸까지 재귀함수로 순회했을 때, 모든 게임판이 다 검은 칸으로 되면 카운트를 하나 증가시키고, 하나라도 흰 칸이 남아있으면 카운트를 증가시키지 않는다.

 

 

처음에 입력을 통해 게임판 정보를 받을 때, '.'인 경우에는 그 좌표를 저장하기 위해 x좌표는 arrx 배열에, y좌표는 arry 배열에 저장하였다. 그래서 재귀함수를 통해 순회를 할 때 흰 칸이었던 좌표들만 찾아서 차례대로 방문하도록 하기 위해서이다. 흰 칸 개수만큼 인덱스 변수 idx를 증가시킨다.

idx = 초반의 총 흰 칸 개수

        for(int h=0;h<H;h++){
            char ch[21]="";
            scanf("%s",ch);
            
            for(int w=0;w<W;w++){
                if(ch[w]=='#'){
                    arr[h][w]=1;
                }
                else if(ch[w]=='.'){
                    arr[h][w]=0;
                    arrx[idx]=w;
                    arry[idx]=h;
                    idx++;
                }
            }
        }

재귀 함수를 호출할 때는 이 인덱스를 하나씩 증가시켜가며 인자로 넘겨준다. 그러면 재귀함수 내에서는 이 인덱스 위치의 흰 칸 좌표(arrx[idx], arry[idx])를 찾아서 해당 칸을 L블럭으로 채울 수 있는지 확인한다.

 

그렇다면 재귀함수의 베이스 조건 즉, 탈출조건은 이 인덱스가 처음의 흰 칸 개수와 같아질 때(모든 흰 칸을 다 순회했을 때)가 될 것이다.

 

 

 

 

 

 

전체 코드 

#include <stdio.h>
int x[3][4][2]={
    {{0,1},{0,1},{-1,0},{-1,0}},  // (1) (2) (3) (4)
    {{0,1},{-1,-1},{-1,0},{1,1}}, // (5) (6) (7) (8)
    {{-1,-1},{0,1},{1,1},{-1,0}}  // (9) (10) (11) (12)
};
int y[3][4][2]={
    {{-1,0},{1,0},{0,1},{0,-1}},  // (1) (2) (3) (4)
    {{1,1},{0,1},{-1,-1},{0,-1}}, // (5) (6) (7) (8)
    {{-1,0},{-1,-1},{0,1},{1,1}}  // (9) (10) (11) (12)
};
int C,H,W;
int cnt,idx;
int arrx[400];
int arry[400];
void recursive(int arr[][W],int index){

    if(index==idx){
        for(int i=0;i<idx;i++){
            if(arr[arry[i]][arrx[i]]==0){
                return;
            }
        }
        cnt++;
        return;
    }
    
    int tx=arrx[index];
    int ty=arry[index];
    
    if(arr[ty][tx]==1){
        recursive(arr,index+1);
        return;
    }
    
    for(int i=0;i<3;i++){
        for(int j=0;j<4;j++){
            int x1=tx+x[i][j][0];
            int y1=ty+y[i][j][0];
            
            int x2=tx+x[i][j][1];
            int y2=ty+y[i][j][1];
            
            if(x1<0 || x1>=W || y1<0 || y1>=H || arr[y1][x1]==1)
                continue;
            
            if(x2<0 || x2>=W || y2<0 || y2>=H || arr[y2][x2]==1)
                continue;
            
            arr[ty][tx]=arr[y1][x1]=arr[y2][x2]=1; // L블럭으로 채우는 행위
          
            recursive(arr,index+1); // 그 다음 흰 칸으로 넘어간다(재귀)
        
            arr[ty][tx]=arr[y1][x1]=arr[y2][x2]=0;
        }
    }
}
int main(void){
    
    scanf("%d",&C);
    
    for(int i=0;i<C;i++){
        scanf("%d %d",&H,&W);
        int arr[H][W];
        cnt=0;
        idx=0;
                
        for(int h=0;h<H;h++){
            char ch[21]="";
            scanf("%s",ch);
            
            for(int w=0;w<W;w++){
                if(ch[w]=='#'){
                    arr[h][w]=1;
                }
                else if(ch[w]=='.'){
                    arr[h][w]=0;
                    arrx[idx]=w;
                    arry[idx]=h;
                    idx++;
                }
            }
        }

        recursive(arr,0);
        printf("%d\n",cnt);
    }
}