[알고스팟] BOARDCOVER - 게임판 덮기 (C++)

문제

algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

풀이

흰 칸들을 4가지 모양(회전하면 네 가지 모양이 나옴)으로 덮을 경우 가능한 경우 수를 구하는 문제.

해당 문제는 다음과 같이, 한 빈칸을 네 가지 경우로 채우는 재귀 함수를 구현한다.

 

4가지 경우의 블록, 빨간 부분이 현재 호출된 칸의 위치

 

 빨간 부분이 호출된 칸이고, 그 칸과 인접한 1,2번 블록을 채우는 네 가지 블록 모델이다.

 

 이렇게 네가지 경우 이외는 생각해 주지 않아도 되는 이유는 흰 칸의 위치를 찾는 함수는 현재 위치부터 column을 +1씩 증가시키며 찾도록 구현하기 때문이다. 따라서 빨간 칸의 위치가 호출되었다면 이전의 칸들은 모두 채워져 있는 것이므로 그 이후의 칸을 채우는 네 가지 경우로 분류한다.

 

blockModel에 해당 블록들의 1,2번 블록의 빨간 블록부터의 상대 위치 값을 넣어준다.

 

FindWhiteBlock을 통해 다음 흰블록을 찾고 찾았다면 true, 보드가 끝났다면 false를 반환한다. 이 함수를 구현할 때 else를 제대로 못 붙여서 한참을 오류와 씨름했다...

 

CountCoverWhite에서는 4가지 경우를 돌면서 경곗값과 블록이 놓일 칸이 흰색인지 확인한다. 만약 블록을 둘 수 있다면 현재 총 흰 칸의 개수를 -3해 주고 검은 칸을 채워준 뒤 다음 흰 칸을 찾아 재귀 호출해준다. 호출이 끝나면 변경한 값들은 복구시켜준다. 구현할 때 흰 칸이 모두 채워진 경우 바로 1을 반환시켜서, whiteNum을 복구시켜주지 못해 또 한참 헤맸다... 전역 변수를 쓰는 것을 조심해야 하는 이유를 뼈저리게 느꼈다.

 

물론 흰 칸의 개수가 3의 배수가 아닌 경우와 흰 칸이 없는 경우는 바로 0을 출력시킨다.

 

풀이는 빨리 생각했지만 코드로 구현한 것이 너무 조잡한 느낌이다. 만약 코드가 읽기 힘들다면 죄송합니다 ㅠㅠ

 

결과: 0ms

 

코드

	#include<iostream>
	#include<string.h>
	using namespace std;
	char board[20][20];
	int height, width;
	int whiteNum;
	int blockModel[4][2][2] ={{{1,0},{1,1}}, {{0,1},{1,1}},{{1,-1},{1,0}},{{0,1},{1,0}} }; //row, column순
	bool FindWhiteBlock(int &r, int &c){
	int nextRow=r, nextCol=c;
	while(1){
	if(board[nextRow][nextCol] == '.'){
	r = nextRow;
	c = nextCol;
	return true;
	}
	if(nextCol < width){
	if(nextCol == width-1){
	if(nextRow == height-1)
	return false; //다음 흰 블록을 찾지 못함-> 끝남
	nextCol=0;
	++nextRow;
	}else
	++nextCol;
	}
	}
	return false;
	}
	int CountCoverWhite(const int r,const int c){
	int ret=0;
	int firstBlockRow, firstBlockCol, secondBlockRow, secondBlockCol;
	int nextRow, nextCol;
	for(int i=0; i<4 ; ++i){
	firstBlockRow = r+blockModel[i][0][0];
	firstBlockCol = c+blockModel[i][0][1];
	secondBlockRow = r+blockModel[i][1][0];
	secondBlockCol = c+blockModel[i][1][1];
	if( secondBlockRow< height && 0<=firstBlockCol && firstBlockCol<width&& secondBlockCol <width )
	if(board[firstBlockRow][firstBlockCol] == '.'&& board[secondBlockRow][secondBlockCol] == '.'){
	whiteNum -= 3;
	if(whiteNum ==0){
	whiteNum +=3;
	return 1;
	}
	board[r][c] = board[firstBlockRow][firstBlockCol] = board[secondBlockRow][secondBlockCol] ='#';
	nextRow =r; nextCol =c;
	if(FindWhiteBlock(nextRow, nextCol))
	ret += CountCoverWhite(nextRow, nextCol);
	whiteNum +=3;
	board[r][c] = board[firstBlockRow][firstBlockCol] = board[secondBlockRow][secondBlockCol] = '.';
	}
	}
	return ret;
	}
	int main(){
	int testNum;
	int startRow, startCol;
	cin>>testNum;
	for(int i=0; i<testNum ; ++i){
	cin>>height>>width;
	whiteNum =0;
	for(int j=0; j<height ; ++j)
	for(int k=0; k<width ; ++k){
	cin>>board[j][k];
	if(board[j][k] == '.')
	++whiteNum;
	}
	if(whiteNum %3 != 0 || whiteNum ==0)
	cout<<'0'<<'\n';
	else{
	startRow =0;
	startCol =0;
	FindWhiteBlock(startRow, startCol);
	cout<<CountCoverWhite(startRow, startCol)<<'\n';
	}
	}
	return 0;
	}

view raw BOARDCOVER.cpp hosted with ❤ by GitHub