(출처) https://www.algospot.com/judge/problem/read/BOARDCOVER
첫번째 생각 : 위 그림과 같은 L형 격자 총 4가지 모양을 모든 빈칸에(최대 48개) 하나 하나마다 넣어보면서 말그대로 모든 경우의 수를 구하는 방법을 생각했다. 즉 모든 경우의 수를 구해 그 중 완벽하게 빈칸을 매울 수 있는 경우만 따로 세주는 것. 하지만 이러면 4^50 = 2^100, 경이나 해 단위는 우습게 뛰어넘는 엄청나게 많은 수를 검사해야되서 바로 포기.
두번째 생각 : 경우의 수를 줄이기위해서 주어진 맵에서 (0,0) 좌표부터 네모격자로 지나가면서 빈칸이 4개인 경우, 3개인 경우, 2개 미만인 경우로 나눠서 각각 처리를 다르게하면서 경우의 수를 세는 법을 생각했다. 이때 탐색은 가장 윗 줄의 가장 첫번째 빈칸(기준점)에서부터 시작하도록하고 해당 칸은 반드시 선택하도록 강제했다. 예를들어 현재 네모격자에 빈칸이 3개인데 만약 기준점이 비어있다면 기준점은 반드시 채워져야하므로 해당 3칸은 반드시 모두 선택해버리지만, 기준점 칸이 이미 채워져있는 상태에서 빈칸이 3개일 경우 네모격자는 그냥 건너뛰거나 3칸을 채워버리거나 2가지의 경우의 수를 선택하게된다. 또한 기준점은 반드시 선택되어야하므로 네모격자에 기준점이 비어있는 상태로 빈칸이 3개 미만이였다면, 해당 경우의 수는 더 이상 게임판을 덮을 수 없는 경우로 판단하고 탐색을 종료한다. 즉 기준점을 기점으로 순서를 강제하며 경우의 수를 탐색하기때문에 특정 중복을 피할 수 있고 모든 경우의 수를 탐색할 수 있다고 판단했다.
경우의 수도 대충 어림 잡아도 한줄에 4^10 = 2^20 = 약 100만 정도이고 첫번째 줄을 완성시키면서 어차피 밑의 칸들은 자동적으로 칸들이 채워질 것이기때문에 4개의 빈칸을 네모격자가 마주치는 횟수는 점점 적어질 것으로 판단하여 해당 방법으로 충분히 2초안 탐색이 가능할 것이라고 결론지었다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;
void printvector(vector<vector<int>>& board) {
printf("-----------");
for (auto iter = board.begin(); iter != board.end(); iter++) {
printf("\n");
for (auto iter2 = (*iter).begin(); iter2 != (*iter).end(); iter2++) {
if (*iter2 == 1) printf(".");
else printf("X");
}
}
printf("\n");
printf("-----------\n");
}
int model[3][4] = { {1,0,1,1},{0,1,1,0},{0,1,1,1} }; // ㄴ자,ㄱ대칭자,ㄱ자 순 model 배열
int boardcover(vector<vector<int>>& board, int y, int x, int white) {
//base case
int count = 0;
if (white == 0) return 1;
int type = -1;
int maxX = board[0].size() - 1, maxY = board.size() - 1;
if (x >= maxX) {
if (y == maxY - 1) return 0;
else {
x = 0;
y += 1;
}
}
for (int temp_y = y; temp_y < maxY; temp_y++) {
for (int temp_x = 0 + x; temp_x < maxX; temp_x++) {
x = 0;
int check = board[temp_y][temp_x] + board[temp_y][temp_x + 1] + board[temp_y + 1][temp_x] + board[temp_y + 1][temp_x + 1];
if (0 < check && check <= 2 && board[temp_y][temp_x] == 1) return 0;
if (check == 3) {
type = 0;
x = temp_x, y = temp_y;
break;
}
if (check == 4) {
type = 1;
x = temp_x, y = temp_y;
break;
}
}
if (type != -1) break;
}
if (type == 0) {
if (board[y][x] != 1) {
vector<vector<int>> tempboard(board);
tempboard[y][x + 1] = tempboard[y + 1][x] = tempboard[y + 1][x + 1] = 0;
//printvector(tempboard);
count += boardcover(tempboard, y, x + 1, white - 3);
//printvector(board);
//check가 3이고 기준점이 빈칸이 아닐때 경우의 수는 2가지로 나누어짐. 남은 3칸을 채우는 경우를 확인하고나면 재귀에서 나와 3칸을 채우지않는 경우를 검사
count += boardcover(board, y, x + 1, white);
}
else {
board[y][x] = board[y][x + 1] = board[y + 1][x] = board[y + 1][x + 1] = 0;
//printvector(board);
count += boardcover(board, y, x + 2, white - 3);
}
}
if (type == 1) {
for (int i = 0; i < 3; i++) {
int dot_y = y + model[i][0], dot_x = x + model[i][1], dot2_y = y + model[i][2], dot2_x = x + model[i][3];
vector<vector<int>> tempboard(board);
tempboard[y][x] = tempboard[dot_y][dot_x] = tempboard[dot2_y][dot2_x] = 0;
//printvector(tempboard);
count += boardcover(tempboard, y, x + 1, white - 3);
//printvector(board);
}
}
return count;
}
int main() {
int testcase;
scanf("%d", &testcase);
for (int i = 0; i < testcase; i++) {
int H, W;
scanf("%d %d", &H, &W);
if (W <= 0) { printf("0\n"); continue;}
vector<vector<int>> board(H); // board에서 1은 빈칸, 0은 막힌 칸
int white = 0;
for (int y = 0; y < H; y++) {
char temp[21];
scanf("%s", temp);
for (int x = 0; x < W; x++) {
if (temp[x] == '.') {
board[y].push_back(1);
++white;
}
else board[y].push_back(0);
}
}
if (white % 3 != 0) {
printf("0\n");
continue;
}
int ret = boardcover(board, 0, 0, white);
printf("%d\n", ret);
}
return 0;
}
기억하고 싶은 점
생각보다 구현이 쉽지 않아서 시간이 오래 걸렸는데 부분문제의 재귀처리를 확실하게 이미지화 하지않고 무턱대고 코드를 짰던게 오히려 오류와 버그가 많이 생겨서 더 시간을 잡아먹었던 것 같다. 어떤 부분을 반복시켜야하고 어떤 부분에서 새로운 부분문제로 진입해야하는지, 또 기저사례가 언제인지 명확하게 이미지를 그려야 할 것 같다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;
void printvector(vector<vector<int>>& board) {
printf("-----------");
for (auto iter = board.begin(); iter != board.end(); iter++) {
printf("\n");
for (auto iter2 = (*iter).begin(); iter2 != (*iter).end(); iter2++) {
if (*iter2 == 1) printf(".");
else printf("X");
}
}
printf("\n");
printf("-----------\n");
}
int boardcover(vector<vector<int>> &board, int white) {
int move[4][4] = { {0,1,1,1}, {0,1,-1,1}, {1,0,1,1},{1,0,0,1} }; // 0번째부터 ㄴ자, ㄴ대칭자, ㄱ자, ㄱ대칭자
int count = 0;
int maxX = board[0].size() - 1, maxY = board.size() - 1;
//기저사례
if (white == 0) return 1;
if (white < 3) return count;
for (int y = 0; y < maxY + 1; y++) {
for (int x = 0; x < maxX + 1; x++) {
if (board[y][x] == 0) continue; // 가리키고 있는 좌표가 막힌벽이라면 그냥 통과
for (int i = 0; i < 4; i++) {
int dot_x = x + move[i][0], dot_y = y + move[i][1], dot2_x = x + move[i][2], dot2_y = y + move[i][3];
if (dot_x < 0 || dot2_x < 0 || dot_x > maxX || dot2_x > maxX || dot_y > maxY || dot2_y > maxY) continue;
if (board[dot_y][dot_x] == 0 || board[dot2_y][dot2_x] == 0) continue;
vector<vector<int>> temp_board(board);
temp_board[y][x] = temp_board[dot_y][dot_x] = temp_board[dot2_y][dot2_x] = 0;
printvector(temp_board);
count += boardcover(temp_board, white - 3);
}
return count;
}
}
}
int main() {
int testcase;
scanf("%d", &testcase);
for (int i = 0; i < testcase; i++) {
int H, W;
scanf("%d %d", &H, &W);
if (W <= 0) { printf("0\n"); continue;}
vector<vector<int>> board(H); // board에서 1은 빈칸, 0은 막힌 칸
int white = 0;
for (int y = 0; y < H; y++) {
char temp[21];
scanf("%s", temp);
for (int x = 0; x < W; x++) {
if (temp[x] == '.') {
board[y].push_back(1);
++white;
}
else board[y].push_back(0);
}
}
if (white % 3 != 0) {
printf("0\n");
continue;
}
int ret = boardcover(board, white);
printf("%d\n", ret);
}
return 0;
}다른 방식의 구현
