BOARDCOVER(C언어)

BOARDCOVER

C++ 이 아닌 C로 코드를 짜려고 하니까 함수의 인자도 많아지고, 변수도 전부 앞에 선언하고 해서 복잡해졌다.

완전 탐색임에도 불구하고, 아이디어를 생각하고 구현하는데 좀 시간이 걸렸다.

문제를 푼 키워드는, 맨왼쪽상단의 값에서 시작한다고 생각한다는 점이었다.

맨 왼쪽 상단이 비어있는 곳에서 4가지의 블럭 경우를 생각하며 채워넣어 갔다.

ㄴ 모양, ㄱ 모양, 그리고 이 두 모양의 좌우로 뒤집은 모양을 dx, dy 를 이용해서 담았다. 

그리고 한칸씩 검사해나가면서 그 칸이 차있는지 그렇지 않은질르 탐색하면서, 

비어있으면 채우고, 아니면 그냥 지나가도록 재귀함수를 만들었다.

가로로 쭉 탐색하였을 경우 다음 줄로 넘어가는 부분을 재귀함수의 if (y==w) 를 통해서 구현했고, 맨 마지막까지 다 채우고 다음 줄로

넘어가게 되면 맨 왼쪽 하단보다 한칸 아래칸으로 이동하게 되므로 그 부분을 기저 조건으로 지정했다.

- 시간복잡도

비어있는 칸에 놓을 수 있는 방법의 수 = 4가지

문제에서 빈칸의 최대수는 50개이고, 이러한 빈칸을 채울 블럭의 갯수는 50/3 = 16가지

따라서 모든 경우의 수는 최대 4^16 = 2^32개가 된다. 

사실 처음에 코드 짤 때 시간이 엄청 크게 나올 것 같아서 고민을 많이 했었다.

시간 복잡도를 봤을 때는 제한 시간 내에 구할 수가 없다. 하지만 종만북 설명에 따르면 선택할 수 있는 블록 배치가 제한된다(범위 초

과와 같은) 그래서 실질적으로는 2가지 방법으로 밖에 배치할 수 없기 때문에 시간이 크게 단축된다.

<정답 코드 - C >

#include<stdio.h>
void making_map(int (*map)[21],int x, int y, int h, int w, int* sum);
int dx[4][3] = {
    { 0,0,1 } ,{ 0,0,1 },{ 0,1,1 },{0,1,1}
};
int dy[4][3] = {
    { 0,1,0 },{ 0,1,1 },{ 0,0,1 },{0,0,-1}
};
int main()
{
    //freopen("input.txt", "r", stdin);
    int i, j, tc,t;
    char tmp;
    int h, w, sum;
    int map[21][21];
    scanf("%d", &tc);
    for (t = 1; t <= tc; t++) {
        scanf(" %d %d", &h, &w);
        sum = 0;
        //map 입력받기
        for (i = 0; i < h; i++) {
            for (j = 0; j < w; j++) {
                scanf(" %c", &tmp);
                if (tmp == '#')
                    map[i][j] = 1;
                if (tmp == '.')
                    map[i][j] = 0;
            }
        }
 
        making_map(map,0, 0, h, w, &sum);
 
        printf("%d\n", sum);
    }
 
    return 0;
}
 
void making_map(int(*map)[21], int x, int y, int h, int w, int* sum)
{
    int i, j, go, nx, ny;
 
    //다음줄로 넘어가기
    if (y == w) {
        x++;
        y = 0;
    }
 
    //모든줄을 다 채웠을 때
    if (x == h && y == 0) {
        (*sum)++;
        return;
    }
 
    //왼쪽 상단의 값이 이미 꽉 찼을 때
    if (map[x][y] == 1)
    {
        making_map( map,x,  y + 1, h, w, sum);
    }
 
    //왼쪽 상단의 값이 꽉 차지 않았을 때
    if (map[x][y] == 0) {
        // i 를 통해서 4개의 모양중 1개 선택
        for (i = 0; i < 4; i++) {
            go = 1;
            for (j = 0; j < 3; j++) 
            {
                nx = x + dx[i][j];
                ny = y + dy[i][j];
                //모양중 하나라도 빈칸이 아닐 때
                if (map[nx][ny] != 0) 
                {
                    go = 0;
                    break;
                }
                if (nx >= 0 && nx < h && ny >= 0 && ny < w) { ; }
                //모양중 하나라도 범위를 벗어날때
                else { go = 0; break; }
            }
 
            if (go)
            {
                //모양을 꽉 채우기
                for (j = 0; j < 3; j++)
                {
                    nx = x + dx[i][j];
                    ny = y + dy[i][j];
                    map[nx][ny] = 1;
                }
                making_map(map,x, y + 1, h, w, sum);
                //꽉 채웠던 모양 다시 비우기
                for (j = 0; j < 3; j++)
                {
                    nx = x + dx[i][j];
                    ny = y + dy[i][j];
                    map[nx][ny] = 0;
                }
 
            }
        }
    }
 
 
}