[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. 결과
왜 안되냐..
Author And Source
이 문제에 관하여([Algorithm] ♟️게임판 덮기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kha0318/Algorithm-게임판-덮기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)