6.6 게임판 덮기

(어렵다. 몹시 하아...)

문제를 보고 완전 탐색으로 풀지 결정을 내렸으면 아이디어와 규칙을 생각해야한다.

아이디어 생각시 중복을 피하기 위해선! 정해진 규칙에 의해서 차례대로 진행해야한다

이 문제에선 블록을 놓을 시 왼쪽을 기준으로 또한 가장 상단을 기준으로 처음의 위치를 찾는다.

그렇게 된다면 그 상태에서 놓을 수 있는 블록의 모양은 4가지로 정의되며, 

이것을 분명히 반복문안에서 차례대로 사용해야 하므로 

자료구조를 잘 표 현 해 야 한 다 . ! ! !

여기서는 3차원 배열을 사용해서 나타내었다. 

(x,y 좌표 2차원 + 갯 수를 나타내는 1차원 = 3차원 )

그러면 완전 탐색 슈도 코드를 이용해야한다.

int func_name(vactor<int> para ...) { if (기저조건) return 1; ... 설정한 기준에 맞는 최초 위치 찾기 ... int ret = 0; for (int i = 0; i < 반복문 종료조건; ++i) { 파라미터로 넘겨온 자료형에 변화 ret += func_name(para ...); 그 변화를 초기화 반복문 진행 } }

이런 식으로 작성을 해야한다.

반드시!

01. 아이디어와 규칙을 정하고

02. 기저조건을 확인하고

03. 반복문의 파라미터로 쓸 자료형을 정하고

04. 위의 코드대로 작성하도록...

#include<iostream> #include<vector> #include<string> #pragma warning(disable:4996) using namespace std; int H, W; // 주어진 칸을 덮을 수 있는 네 가지 방법 // 블록을 구성하는 세 칸의 상대적 위치 (dy, dx)의 목록 const int coverType[4][3][2] = { { { 0,0 },{ 1,0 },{ 0,1 } }, { { 0,0 },{ 0,1 },{ 1,1 } }, { { 0,0 },{ 1,0 },{ 1,1 } }, { { 0,0 },{ 1,0 },{ 1,-1 } } }; // board의 (y,x)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다. // delta = 1 이면 덮고, delta = -1 이면 덮었던 블록을 없앤다. // 만약 블록이 제대로 덮이지 않는 경우 ( 게임판 밖으로 나가거나, // 겹치거나, 검은판을 덮을 때) false를 반환한다. bool set(vector<vector<int>> &board, int y, int x, int type, int delta) { bool ok = true; for (int i = 0; i < 3; ++i) { const int ny = y + coverType[type][i][0]; const int nx = x + coverType[type][i][1]; if (ny < 0 || ny >= board.size() || nx < 0 || nx >= board[0].size()) ok = false; else if ((board[ny][nx] += delta) > 1) ok = false; } return ok; } // board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환한다. // board[i][j] = 1 이미 덮인 칸 혹은 검은 칸 // board[i][j] = 0 아직 덮이지 않은 칸 int cover(vector<vector<int>> & board) { int y = -1, x = -1; for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (board[i][j] == 0)// 흰 칸 { y = i; x = j; break; } if (y != -1) break; } } // 기저 사례 : 모든 칸을 채웠으면 1을 반환한다. if (y == -1) return 1; int ret = 0; for (int type = 0; type < 4; ++type) { //만약 board[y][x]를 type 형태로 덮을 수 있으면 재귀 호출 한다. if (set(board, y, x, type, 1)) ret += cover(board); //덮었던 블록을 치운다. set(board, y, x, type, -1); } return ret; } void main() { int testCase; char temp; FILE *f; f = fopen("input.txt", "r"); fscanf(f, "%d", &testCase); vector<vector<int> > input; for (int t = 0; t < testCase; ++t) { input.clear(); fscanf(f, "%d %d\n", &H, &W); for (int i = 0; i < H; ++i) { vector<int> vec; for (int j = 0; j < W; ++j) { fscanf(f, "%c", &temp); if (temp == '#') { vec.push_back(1); } else { vec.push_back(0); //input[i][j] = 0; } } fscanf(f, "%c", &temp); input.push_back(vec); } printf("%d\n", cover(input)); } }