[Algorithm] ♟️게임판 덮기

1. 문제 해석

흰색 판을 3칸짜리 L모양 블럭으로 덮는 경우의 수

회전 가능, 겹치기 불가능

입력

C(테스트 케이스)
H(세로) W(가로)
#(검은칸).(흰칸)

출력

게임판 덮는 경우의 수

2. 아이디어

💡 L모양 블럭을 회전시 4가지 모양 가능
💡 흰색과 검은색을 분리 후에, L모양 블럭으로 덮을 수 없는 곳과 있는 곳을 구분
💡 조합을 이용하여 풀이 : 재귀함수

3. 풀이

1) L모양 가능한 경우 배열로 선언

int coverType[][][] = {
{{0,0},{1,0},{0,1}},
{{0,0},{0,1},{1,1}},
{{0,0},{1,0},{1,1}},
{{0,0},{1,0},{1,-1}}
};

2) board의 맨 왼쪽 상단부터 탐색하여 board가 0이면 비어있는 흰색 칸임 (중복 방지 위해)

for(int i=0; i<board.length; ++i) {
			for(int j=0; j<board[i].length; ++j) {
				if(board[i][j] == 0) {
					y = i;
					x = j;
					break;
				}
			}
			if(y != -1)
				break;
		}

3) 비어있는 흰색 칸의 주변 3칸을 확보해 L모양을 넣고 count한 후, 다시 빼기

for(int type =0; type<4; type++) {
			if(set(board,y,x,type,1))
				ret+=cover(board);
			set(board,y,x,type,-1);
	}

4. 코드

import java.io.*;

public class BoardCover {
	static int c,w,h;
	static int coverType[][][] = {
			{{0,0},{1,0},{0,1}},
			{{0,0},{0,1},{1,1}},
			{{0,0},{1,0},{1,1}},
			{{0,0},{1,0},{1,-1}}
			};
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		c = Integer.parseInt(br.readLine());
		int result[] = new int[c];
		
		for(int i=0; i<c; i++) {
			String s[] = br.readLine().split(" ");
			h = Integer.parseInt(s[0]);
			w = Integer.parseInt(s[1]);
			int board[][] = new int[h][w];
			
			for(int k=0; k<h; k++) {
				String str = br.readLine();
				for(int j=0; j<w; j++) {
					board[i][j] = str.charAt(j) == '#'? 1:0;
				}
			}
			
			result[i] = cover(board);
		}
		
		for(int i=0; i<c; i++)
			System.out.println(result[i]);
	
	}
	
	public static boolean set(int board[][],int y, int x, int type, int delta) {
		boolean ok = true;
		
		for(int i=0; i<3; ++i) {
			int ny = y + coverType[type][i][0];
			int nx = x + coverType[type][i][1];
			
			if(ny<0 || ny>=board.length || nx<0 || nx>= board[0].length)
				ok = false;
			else if((board[ny][nx] += delta) > 1)
				ok = false;
		}
		
		return ok;
	}
	
	public static int cover(int board[][]) {
		int y = -1, x = -1;
		
		for(int i=0; i<board.length; ++i) {
			for(int j=0; j<board[i].length; ++j) {
				if(board[i][j] == 0) {
					y = i;
					x = j;
					break;
				}
			}
			if(y != -1)
				break;
		}
		
		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;
	}
}

5. 결과

왜 안되냐..