[종만북][알고스팟] BOARDCOVER(게임판 덮기) - 브루트포스(BruteForce) JAVA

https://www.algospot.com/judge/problem/read/BOARDCOVER

algospot.com :: BOARDCOVER

코드설명

브루트포스를 활용합니다.

 

문제에서 유의해야할 점들입니다.

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;
	}
}