티바이트



문제 주소 : https://algospot.com/judge/problem/read/BOARDCOVER

(알고스팟)


문제 이해

격자 모양의 게임판이 주어진다.

입력으로 주어지는 게임판에는 검은 칸과 흰 칸이 있으며

이 중에서 흰 칸을 아래 4가지 모양의 블록으로 채울 때

남은 칸을 모두 채울 수 있는 경우의 수를 구하는 문제이다.

가능한 답을 완전탐색(exhaustive search)해야 한다.



전략

흰 칸을 블록으로 모두 채운 경우에서

이 중 하나의 블록을 제외하여도 나머지 블록은 칸을 모두 채우고 있는 것을 볼 수 있다.

블록이 4가지 모양에 따라 가지를 뻗어 나가면서 탐색한다.



블록 하나를 배치한 뒤 남은 흰 칸을 재귀호출로 넘긴다.

다시 블록 하나를 배치하고 남은 흰 칸을 재귀호출로 넘긴다.


만약 칸을 더 이상 채울 수 없다면 재귀에서 탈출한다.

그리고 다음 단계에서 다른 모양으로(블록은 회전 때문에 4가지 모양이 있다)

흰 칸 채우기를 수행하기 위해 다시 재귀호출을 한다.


만약 칸을 모두 채웠다면 1을 반환한다.

재귀 구조에서 이 수를 누적하여 계산한다.


풀이


가능한 블록의 모양이 위 그림과 같으므로

함수의 구조는 대략 이렇게 될 것이다.

insert (map, free) {  //2차원배열, 남은 흰 칸 수

    int count = 0;

    if (남은 칸이 3의 배수가 아니면) {

        return 0;

    }

    if (남은 칸이 3이고, 채울 수 있는 형태이면) {

        return 1;

    }

    if (남은 칸이 3이고, 채울 수 는 형태이면) {

        return 0;

    }

    if (1번 블록을 채울 수 있으면) {

        1번 블록을 채운다;

        count += insert(map, free-3);

        1번 블록을 해제한다:

    }

    if (2번 블록을 채울 수 있으면) {

        2번 블록을 채운다;

        count += insert(map, free-3);

        2번 블록을 해제한다:

    }

    if (3번 블록을 채울 수 있으면) {

        3번 블록을 채운다;

        count += insert(map, free-3);

        3번 블록을 해제한다:

    }

    if (4번 블록을 채울 수 있으면) {

        4번 블록을 채운다;

        count += insert(map, free-3);

        4번 블록을 해제한다:

    }

    return count;

}


이 때 생각해 볼 점은, 처음에 블록을 어디부터 채우고,

그 다음에는 또 어디부터 채울 것이냐다.

여기서는 상단, 좌측을 우선하여 블록을 채우기로 했다.

블록을 채우는 순서는 경우의 수에 영향을 미치지 않기 때문에 하단부터 채워도 결과는 같다.


상단,좌측을 우선하여 블록을 채울 때

기준이 되는 점(초록색)과 추가로 검사해야 하는 점(회색)은 아래그림과 같다.




소스코드(C++)


(설명의 블록 번호와 아래 소스코드의 블록 번호는 다릅니다)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
#include <iostream>
#include <string>
 
using namespace std;
 
int insert(int **map, int row, int col, int free)
{
 
    //맨윗줄 맨왼쪽 구함
    int tx; //targetX
    int ty; //targetY
    for (int i = 1; i < row-1; i++) {
        for (int j = 1; j < col-1; j++) {
            if (map[i][j] == 1) {
                tx = j;
                ty = i;
 
                //exit
                i = row - 1;
                j = col - 1;
            }
        }
    }
 
    bool p1 = false//패턴1 : 남, 동
    bool p2 = false//패턴2 : 남, 남동
    bool p3 = false//패턴3 : 동, 남동
    bool p4 = false//패턴4 : 남, 남서
 
    if (map[ty+1][tx] && map[ty][tx+1]) p1 = true;
    if (map[ty+1][tx] && map[ty+1][tx+1]) p2 = true;
    if (map[ty][tx+1] && map[ty+1][tx+1]) p3 = true;
    if (map[ty+1][tx] && map[ty+1][tx-1]) p4 = true;
 
 
    //만약 남은칸이 3이고, 채울 수 있는 형태이면, 1 반환
    if (free == 3) {
        if (p1||p2||p3||p4)
            return 1;
        else
            return 0;
    }
 
 
    int count = 0;
 
    if (p1) {
        //채움
        map[ty][tx] = 0;
        map[ty+1][tx] = 0;
        map[ty][tx+1= 0;
        //재귀호출
        count += insert(map, row, col, free-3);
        //채운 것 취소
        map[ty][tx] = 1;
        map[ty+1][tx] = 1;
        map[ty][tx+1= 1;
    }
 
    if (p2) {
        //채움
        map[ty][tx] = 0;
        map[ty+1][tx] = 0;
        map[ty+1][tx+1= 0;
        //재귀호출
        count += insert(map, row, col, free - 3);
        //채운 것 취소
        map[ty][tx] = 1;
        map[ty+1][tx] = 1;
        map[ty+1][tx+1= 1;
    }
    
    if (p3) {
        //채움
        map[ty][tx] = 0;
        map[ty][tx+1= 0;
        map[ty+1][tx+1= 0;
        //재귀호출
        count += insert(map, row, col, free - 3);
        //채운 것 취소
        map[ty][tx] = 1;
        map[ty][tx+1= 1;
        map[ty+1][tx+1= 1;
    }
    
    if (p4) {
        //채움
        map[ty][tx] = 0;
        map[ty+1][tx] = 0;
        map[ty+1][tx-1= 0;
        //재귀호출
        count += insert(map, row, col, free - 3);
        //채운 것 취소
        map[ty][tx] = 1;
        map[ty+1][tx] = 1;
        map[ty+1][tx-1= 1;
    }
 
    return count;
}
 
int main(void)
{
    int num;
    cin >> num;
    while (num--)
    {
        int row;
        int col;
 
        cin >> row >> col;
        row += 2;
        col += 2;
        //동적할당
        int **map = new int*[row];
        for (int i = 0; i < row; i++) {
            map[i] = new int[col];
            for (int j = 0; j < col; j++) {
                map[i][j] = 0;
            }
        }
 
        //입력받기
        for (int i = 0; i < row-2; i++) {
            string str;
            cin >> str;
            for (int j = 0; j < col-2; j++) {
                if (str[j] == '.') {
                    map[i+1][j+1= 1;
                }
            }
        }
 
        
        //자유영역 계산
        //만약 자유영역이 3의 배수가 아니면 기각
        int free = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] == 1)
                    ++free;
            }
        }
 
        int count;
 
        if (free == 0) {
            count = 1;
        }
        else if (free % 3 != 0) {
            count = 0;
        }
        else {
            count = insert(map, row, col, free);
        }
        cout << count << endl;
 
        for (int i = 0; i < row; i++) {
            delete[] map[i];
        }
        delete[] map;
 
    }
    return 0;
}
 
cs



 


  1. 호오

  2. 와.. 신기하네요. 잘 봤습니다.

  3. 피러킴 2016.09.24 01:50

    포스트 잘 봤습니다. 도움이 많이 돼요!

댓글을 다는 공간입니다. (로그인하지 않아도 댓글을 남길 수 있습니다.)



게시판 목록은 좌측상단에 있습니다.

04-13 10:03