https://www.algospot.com/judge/problem/read/BOARDCOVER
algospot.com :: BOARDCOVER
게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이
www.algospot.com
코드설명
브루트포스를 활용합니다.
문제에서 유의해야할 점들입니다.
1. coverType, 즉 격자 모양을 생성할때, 빈칸 중에서 가장위, 그 중에서도 가장 왼쪽에 있는 칸을 처음 채운다고 가정해야 합니다. 따라서 그 왼쪽과 위에 있는 칸은 항상 이미 채워져있다고 가정할 수 있습니다.
처음에 해당 사항을 놓치고, 아래와 같이 하였기에 격자칸을 모두 카운팅하지 못했습니다.
잘못된 블록입니다. 두번째를 보면 {0, 1} 로 처리합니다.
public static int[][][] coverType = {
{
{0, 0},
{0, 1},
{1, 1}
},
{
{0, 1},
{1, 0},
{1, 1}
},
{
{0, 0},
{1, 0},
{1, 1}
},
{
{0, 0},
{0, 1},
{1, 0}
}
};올바르게 바꾼 방식입니다. 가장 왼쪽 칸은 항상 채우도록 하고, 가장 왼쪽 칸 이전은 반드시 채우는 방안으로 해야 합니다. 이유는 다시는 이전 칸으로 돌아가지 않기 때문입니다. 즉, 앞으로는 이전 칸은 전혀 고려하지 않고 앞으로의 칸만 고려할 것 입니다.
public static int[][][] block = new int[][][]
//[4][][]
{
// [4][3][]
{
//[4][3][2]
{0, 0},
{1, 0},
{1, 1}
},
{
{0, 0},
{0, 1},
{1, 0}
},
{
{0, 0},
{0, 1},
{1, 1}
},
{
{0, 0},
{1, -1},
{1, 0}
}
};
만들다보면, 이전의 격자 칸의 모양이 만약 맞지 않으면 어떻게하지? 라는 고민이 생길 수 있는데 이전 칸은 반드시 채워졌다고 가정하면서 진행하므로 앞으로의 채우는 과정만 신경쓰면 됩니다.
2. 매번 아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾습니다. 코드로는 기저사례 부분입니다.
//아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
int r = -1, c = -1;
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
if(board[i][j] == 0) {
r = i;
c = j;
break;
}
}
if(c != -1) break;
}
//기저 사례 ; 모든 칸을 채웠으면 1을 반환한다.
if(c == -1) return 1;
답의 상한을 계산해봅니다.
흰칸이 최대 개수는 50개입니다. 그러므로 [50/3] = 16개의 블록을 놓을 수 있기에 가능한 답의 상환은 4^16 (블록 16개를 총 4개의 경우의 수로 설정할 수 있음) = 2^32 ( 약 40억 .
이를 보면, 도저히 시간 내에 생성할 수 없을 것 같지만, 실제 입력을 손으로 풀어보면 각 단계에서 우리가 선택할 수 있는 블록 배치가 크게 제한됨을 알 수 있습니다. 예를 들어 흰 칸이 6칸 있는 입력이 주어진다면 이 이론상으로는 4^2 = 16가지의 방법이 있어야 하는데 , 실제로는 최대 두가지 방법밖에 없습니다. 흰칸이 48개 있는 예제 입력 3을 보더라도 답이 1,514가 나오기에 시간 안에 답을 구할 수 있음을 알 수 있습니다.
코드
package algorhythm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = 0;
public static char[][] map;
//[4개의 회전방향][3개의 칸][각 요소 2개]
//첫 시작은 ㄱ 모양으로 해서 시계방향으로 회전시킬 것 이다.
//[4][3][2] 형태로 만들 것 입니다.
public static int[][][] coverType = {
{
{0, 0},
{0, 1},
{1, 0}
},
{
{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 IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- > 0) {
st = new StringTokenizer(br.readLine());
int H = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
map = new char[H][W];
for(int i=0;i<H;i++) {
st = new StringTokenizer(br.readLine());
map[i] = st.nextToken().toCharArray();
}
int[][] board = new int[H][W];
for(int i=0;i<H;i++) {
for(int j=0;j<W;j++) {
board[i][j] = (map[i][j] == '#' ? 1 : 0); //만약 # 이면 검은 칸입니다.
}
}
answer = cover(board);
System.out.println(answer);
}
}
//board의 (y, x)를 type번 방법으로 덮거나, 덮었던 블록을 없앤다.
//delta = 1 이면 덮고, -1 이면 덮었던 블록을 없앤다.
//만약 블록이 제대로 덮이지 않은 경우( 게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때) false를 반환한다.
public static boolean set(int[][] board, int r, int c, int type, int delta) {
boolean ok = true;
for(int i=0;i<3;i++) {
int nr = r + coverType[type][i][0];
int nc = c + coverType[type][i][1];
if( nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) {
ok = false;
}
else if( (board[nr][nc] += delta) > 1) {
ok = false;
}
}
return ok;
}
// board의 모든 빈칸을 덮을 수 있는 방법의 수를 반환한다.
// board[i][j] = 1 이미 덮인 칸 혹은 검은 칸
// board[i][j] = 0 아직 덮이지 않은 칸
public static int cover(int[][] board) {
//아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
int r = -1, c = -1;
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[i].length;j++) {
if(board[i][j] == 0) {
r = i;
c = j;
break;
}
}
if(c != -1) break;
}
//기저 사례 ; 모든 칸을 채웠으면 1을 반환한다.
if(c == -1) return 1;
int ret = 0;
for(int type = 0; type < 4; type++) {
//만약 board[y][x]를 type형태로 덮을 수 있으면 재귀 호출한다.
if( set(board, r, c, type, 1) )
ret += cover(board);
//덮었던 블록을 치운다.
set(board, r, c, type, -1);
}
return ret;
}
}
다르게 풀어본 코드입니다. 속도는 첫번쨰 코드보다 느립니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M, H, W;
public static int answer = Integer.MAX_VALUE;
public static int[][] map;
public static char[][] mapInput;
public static int whiteBoxCnt;
public static int[][][] block = new int[][][]
//[4][][]
{
// [4][3][]
{
//[4][3][2]
{0, 0},
{1, 0},
{1, 1}
},
{
{0, 0},
{0, 1},
{1, 0}
},
{
{0, 0},
{0, 1},
{1, 1}
},
{
{0, 0},
{1, -1},
{1, 0}
}
};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- > 0) {
st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
mapInput = new char[H][W];
map = new int[H][W];
for(int i=0;i<H;i++) {
st = new StringTokenizer(br.readLine());
mapInput[i] = st.nextToken().toCharArray();
}
whiteBoxCnt = 0;
for(int i=0;i<H; i++) {
for(int j=0;j<W; j++) {
if(mapInput[i][j] == '#') {
map[i][j] = 1;
}else {
whiteBoxCnt += 1;
map[i][j] = 0;
}
}
}
System.out.println(getBoardCoverCnt(0,0, 0));
}
}
public static int getBoardCoverCnt(int r, int c, int whiteCnt) {
//기저사례 1:
if(c >= W) {
r = r + 1; c = 0;
}
// if(r == H-1 && c == W - 1 && whiteBoxCnt == whiteCnt) {
// return 1;
// }
if(r == H-1 && c == W - 1 && isAllCovered() == true) {
return 1;
}
if(r < 0 || r >= H || c < 0 || c >= W) return 0;
int ret = 0;
if(map[r][c] == 1) { //만약 이미 채워진 칸이라면 칸을 채우지 않고, 다음칸으로 넘어갑니다.
ret += getBoardCoverCnt(r, c + 1, whiteCnt);
return ret;
}
for(int type = 0; type < 4; type++) {
if(map[r][c] == 0) {
boolean isSuccess = cover(r, c, type, +1);
if(isSuccess) {
ret += getBoardCoverCnt(r, c + 1, whiteCnt + 3);
}
cover(r, c, type, -1);
}
}
return ret;
}
public static boolean cover(int r, int c, int type, int value) {
boolean isSuccess = true;
for(int order = 0; order < 3; order++) {
int nr = r + block[type][order][0];
int nc = c + block[type][order][1];
if(nr < 0 || nr >= H || nc < 0 || nc >= W) {
isSuccess = false;
continue;
}
map[nr][nc] += value;
}
return isSuccess;
}
public static boolean isAllCovered() {
for(int i=0;i<H;i++) {
for(int j=0;j<W;j++) {
if(map[i][j] != 1) {
return false;
}
}
}
return true;
}
}