링크 : https://algospot.com/judge/problem/read/BOARDCOVER
문제 읽기
자유롭게 회전 가능.
겹치거나 검은 칸을 덮거나 게임판 밖으로 나가서는 안된다.
게임판이 주어졌을 때 덮을 수 있는 경우의 수.
흰 칸이 3의 배수여야 겹치지 않고 덮을 수 있다.
각 칸마다 모두 4가지의 방법으로 놓을 수 있는데 제한으로 인해 4 이하의 방법으로 블록을 놓을 수 있다.
L 블럭을 구성하는 3칸의 상대적 위치 (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}}
};delta = 1이면 덮고 delta = -1이면 덮었던 블록을 없앤다.
코드
#include <iostream>
#include <vector>
using namespace std;
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}}
};
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;
}
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[0].size(); j++) {
//덮이지 않은 칸이라면 찾아서 break
if (board[i][j] == 0) {
y = i;
x = j;
break;
}
}
if (y != -1) break;
}
//base case : 모든 칸을 채웠다면 1을 반환한다
if (y == -1) return 1;
int ret = 0;
for (int type = 0; type < 4; ++type) {
if (set(board, y, x, type, 1))
ret += cover(board);
set(board, y, x, type, -1);
}
return ret;
}
int main() {
//cin.tie(NULL);
//ios_base::sync_with_stdio(false);
int C, H, W;
char chr;
cin >> C;
for (int test = 0; test < C; test++) {
cin >> H >> W;
int cnt = 0;
//HxH 개의 벡터 배열을 선언한다.
vector<vector<int>> a(H, vector<int>(W,0));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> chr;
if (chr == '#')
a[i][j] = 1;
else {
a[i][j] = 0;
cnt++;
}
}
}
if (cnt % 3 != 0)
cout << 0 << "\n";
else
cout << cover(a) << "\n";
}
return 0;
}
분석
악. 쉽다며..
우선 문제의 coverType 먼저 살펴보자.
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}}
};2x2 배열이라고 생각해보자. 종만북 책 162 페이지의 4가지 경우를 살펴보자. 중심에 알파벳을 써놓았다.
| x | 0 | 1 |
|---|---|---|
| 0 | b | c |
| 1 | d | e |
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;
}배열 벡터를 확인하고 delta를 설정하는 함수이다.
const int ny = y + coverType[type][i][0];에서 b, c, d, e type 타입 중에서 하나를 선택한다. 여기서는 type을 선택했고 type은 총 3개의 단위 블록으로 이어져있으므로 이 3개의 블럭이 모두 유효한 조건 속에 있어야 한다. 따라서 단위블록의 몇번째를 확인할 것인지의 i를 확인하고 여기에서 dy에 해당하는 0번째 인덱스의 값을 가져온 것이다. dx는 자연스럽게 1번째 인덱스의 값을 가져올 것이다.
나머지는 주석으로 확인할 수 있다.
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[0].size(); j++) {
if (board[i][j] == 0) {
y = i;
x = j;
break;
}
}
if (y != -1) break;
}
//base case : 모든 칸을 채웠다면 1을 반환한다
if (y == -1) return 1;
int ret = 0;
for (int type = 0; type < 4; ++type) {
if (set(board, y, x, type, 1))
ret += cover(board);
set(board, y, x, type, -1);
}
return ret;
}문제 읽기에서 확인했다 싶이 중복을 피하기 위해서 체크되지 않은 부분 중에서 가장 윗쪽 && 가장 왼쪽인 부분을 찾아야 했다. 2중 for문을 통해 찾았고 만약 찾지 못했다면 1을 return한다.
찾았다면 거기서 부터 시작하여 set을 이용해 블록을 놓을 수 있는 곳인지 확인하면서 블럭을 놓을 수 있는 방법의 수를 count한다.
추가로 2차원 배열 선언하는 방법 한번 더 확인하고 가자.
vector<vector<int>> vec(행 개수, vector<int>(열 개수, 초기화 값));