[algospot] 게임판 덮기 BOARDCOVER

게임판 덮기 (ID : BOARDCOVER)

---

내 풀이 코드

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int currentHeight, currentWidth;

// ㄱ 자 모양을 4가지 방향으로 덮을 수 있다. 방향 당 3칸을 차지하며, 각 칸의 좌표를 기록해둔 것이다.
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 x, int y, int type, int delta){ // (보드 , x, y, 칸 놓는 타입, 칸을 놓을 것인지 제거할 것인지 결정)
	bool flag = true;
	for(int i = 0; i < 3; i++){
		// 좌표 설정
		int dy = y + coverType[type][i][0];
		int dx = x + coverType[type][i][1];
		
		// 칸을 벗어나면 false
		if(dx < 0 || dx >= currentWidth || dy < 0 || dy >= currentHeight){
			flag = false;
		}
		// 두 번 겹치면 즉, board 값이 1이 넘어가면 false
		// 중요. delta 가 1이라면 보드를 놓는 역할, -1이라면 빼는 역할이 된다. 동시에 조건 확인 까지 해준다.
		else if((board[dy][dx] += delta) > 1){
			flag = false;
		}
	}
	return flag;
	
}


int lCoverNum(vector<vector<int>> &board){
	// 기저사례 : 좌측 상단의 채워지지 않은 칸을 찾아낸다. 없으면 종료
	int y = -1, x = -1;
	
	for(int i = 0; i < currentHeight; i++){
		for(int j = 0; j < currentWidth; j++){
			if(board[i][j] == 0){
				y = i;
				x = j;
				break;
			}
		}
		if (x != -1) break;
	}
	// x 가 여전히 -1 이라면 다 채운 것이므로 1을 반환한다.
	if(x == -1) return 1;
	
	// 재귀 구간
	// 한 가지 타입에 대해서 칸을 채우고 지운다.
	int ret = 0;
	
	for(int type = 0; type < 4; type++){
		if(set(board, x, y, type, 1)) // type 에 해당하는 칸들에 놓을 수 있으면 놓고
			ret += lCoverNum(board); // 재귀
		set(board, x, y, type, -1); // 놓은 칸을 지운다.
	}
	return ret;
}

int main(){
	int C;
	int height[20], width[20], result[30] = {0};
	vector<vector<vector<int>>> board(30, vector<vector<int>>(20, vector<int>(20, 0)));
	
	// 파일 입출력을 위함.
	std::ifstream readFile;
	readFile.open("./boardcover.txt");
	
	cin >> C;
	cin.ignore();

	for(int c = 0; c < C; c++){ // 테스트 케이스 개수 C 만큼 반복
		cin >> height[c];
		cin >> width[c];
		
		cin.ignore();
		
		int countWhite = 0;
		
		for(int h = 0; h < height[c]; h++){
			for(int w = 0; w < width[c]; w++){
				char shopOrDot;
				cin >> shopOrDot;
				if(shopOrDot == '#') {
					board[c][h][w] += 1;
					countWhite += 1;
				}
			}
			cin.ignore();
		}
		
		if(countWhite % 3 != 0) break;
		else if(countWhite == 0) result[c] += 1; // 모든 칸이 검은 색이면, 아무것도 채우지 않는 방법이 있으므로 1개이다. 예외처리
		
		currentWidth = width[c];
		currentHeight = height[c];	
		result[c] = lCoverNum(board[c]);
		
	}
	
	for(int c = 0; c < C; c++){ // 테스트 케이스 개수 C 만큼 반복
		cout << result[c] << endl;
	}
	
}

문제의 간단한 해법

: 그저 무식하게 풀기로 접근했다.

완전 탐색을 하는데, 하얀 칸을 만날 시에 재귀 함수로 그 칸을 넘겨준다. 

해당 칸에서 4개의 모양 중 칠할 수 있는 모양을 다 칠해본다.

다음, 인접한 칸 중 옮겨갈 수 있는 칸으로 옮겨간다.

보드가 다 채워지면, count 를 증가시킨다.

어떠한 방식 / 깨달음 으로 접근했는지 & 사용한 문제 해결 전략

: 처음 무식하게 풀기 로 접근하였을 때의 문제점은 역시 중복하여 세는 경우였다. 이 경우는 저번 문제 (PICNIC) 때와 마찬가지로 특정한 순서를 강제하여 풀이하였다. 재귀를 할 때, 모든 칸에 대하여 하는 것이 아니라 좌측 상단의 칸을 찾아서 그 순서대로 내려가는 형태를 취했다.

: 흰 칸이 3의 배수가 아니라면 0으로 바로 처리하는 것.. 이런 예외 처리가 참 중요해 보인다. 

: 모든 칸이 검은 색이면, 아무것도 채우지 않는 방법이 있으므로 1개이다. 예외처리...

오답 원인

: 결국.. 오타를 찾는 것과의 싸움이었다. 남의 코드를 참고하며 하다보니 오타가 더 잦은 듯 하다. 이번에는 c 와 w 를 잘못 쳤더라

새로이 배운 점

: 처음 접근할 때, vector 를 쓰지 않고 단순 array 로만 접근하였다. 그렇게 하다보니 발생한 문제점은, array 를 reference 로 넘겨줄 때 3차원 array 여서 2차, 3차의 최대 index 가 필요하다는 점이었다. 이를 해결하기 위해 3차원 vector 로 array 를 대체하였다.

: 재귀 함수를 사용하는데 한 함수에 모든 것을 재귀할 필요는 없다는 것을 깨달았다. 이번 경우엔 set 함수가 그러했다.

1. 범위를 벗어나는지 판별

2. 칸을 겹치게 두었는지 판별

3. 2를 판별함과 동시에 칸을 채우거나 비우는 역할

4. 범위를 벗어나거나 칸을 겹치게 두었다면 false 를 반환하여 둘 수 없다는 것을 알려줌

이 네가지는 결국 "재귀" 하는 역할이 아니었다. 이것은 재귀를 수행하는 동안 필요한 정적인 작업일 뿐이었다.

필요한 재귀는 "좌측 상단의 칸을 찾아서 type 에 따라 놓고 / 재귀 / 빼고" 의 형식이었다. set 함수는 이 과정에서 놓고 빼고를 담당하며 자질구레한 조건들도 차지하여 lCoverNum 함수를 더욱 간결하게 만들어 준 것이다.

다른 사람(책)의 코드를 보고 비교

: