[알고리즘] 알고스팟 BOARDCOVER 문제

# 알고리즘을 통한 문제 해결전략 6.5

 

- 이차원 벡터를 처음 사용해봤다!!

- 코드에 대한 이해가 더 필요하다.. 한번 더 풀어볼 것!

#include <iostream>
#include <vector>
using namespace std;

//주어진 칸을 덮을 수 있는 네가지 방법
// 블록을 구성하는 세 칸의 상대적 위치(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이면 덮고, -1이면 덮었던 블록을 없앤다
//만약 블록이 제대로 덮이지 않은 경우(겹치거나, 그림판밖으로나가거나,검은칸 덮을때) false
bool set(vector<vector<int>>& board, int y, int x, int type, int delta);
//board의 모든 빈칸을 덮을 수 있는 방법의 수 반환
//board[i][j]=1 이미 덮인 칸 또는 검은칸
//board[i][j]=0 아직 덮이지 않은 칸
int cover(vector<vector<int>>& board);

int main() {
	int testCase, H, W;
	char ch;
	cin >> testCase;
	
	for (int i = 0; i < testCase; i++) {
		cin >> H>> W;
	
		vector<vector<int>> board;
		for (int m = 0; m < H; m++) {
			vector<int>tmp(W);
			board.push_back(tmp);
		}

		for (int m = 0; m < H; m++) {
			for (int n = 0; n < W; n++) {
				cin >> ch;
				if (ch == '#') board[m][n] = 1;
				else if(ch == '.') board[m][n] = 0;
			}
		}
		int ret = cover(board);
		cout << ret<<endl;

	}
		

}
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[i].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++) {
		//만약 board[y][x]를 type형태로 덮을 수 있으면 재귀호출
		if (set(board, y, x, type, 1))
			ret += cover(board);
		//덮었던 블록을 치운다.
		set(board, y, x, type, -1);
	}
	return ret;
}