문제 주소 : 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 |