게임판 덮기 (골드2)

1. 문제 설명

(1) 게임판 덮기 문제는 아래와 같은 게임판을 이용하여 삼각형( ┌,  ┐, └,  ┘)을 가지고 흰색 칸에 빈틈없이

채울 수 있는 최대 경우의 수를 구하는 것이다.

( 이때, 검은색 칸에는 채울 수 없으며 연속으로 이어져 있다. )

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫 번째 줄에는 문제 입력 수 C를 입력받는다.

 

(2) 두 번째 줄부터는 게임판의 높이 H와 넓이 W를 입력받는다.

( H>=1과 W<=20 )

 

(3) 그 이후 세번째 줄부터는 게임판 크기만큼 흰색과 검은색을 채운다.

( 여기서는 #이 검은색 .이 흰색 )

 

(3) 게임판에 있는 흰칸의 수는 50을 넘지 않아야 한다.

 

(4) 흰 칸에 채워질 도형의 크기는 3칸이므로, 반드시 흰칸의 수는 3배수 이어야 한다.

 

출력 조건

(1) 흰색 칸에 채울 수 있는 최대 경우의 수를 출력한다.

 

입력 예제

3
3 7
# . . . . . #
# . . . . . #
# # . . . # #
3 7
# . . . . . #
# . . . . . #
# # . . # # #
8 10
# # # # # # # # # #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . ## # # # # # # # # #

출력 예제

0
2
1514

 

 

 

3. 풀이 및 코드

: 이 유형의 문제는 항상 특정 순서를 세워서 풀어야 한다.

바로 가장 왼쪽 상단부터 시작하여 삼각형( ┌,  ┐, └,  ┘)을 가지고 하나씩 채우면서 재귀 호출 하는 것이다.

 

또한 삼각형( ┌,  ┐, └,  ┘)은 아래의 표처럼 (0,0) 기준으로 잡고 범위를 체크한다.

	-1	0	1
-1	(-1,-1)	(-1,0)	(-1,1)
0	(0,-1)	(0,0)	(0,1)
1	(1,-1)	(1,0)	(1,1)

또한 삼각형을 넣을때마다 게임판 범위 안에 드는 것인지 흰색과 검은색을 구분하고 삼격형을 넣는 것인지 항상 체크해야

한다.

 

public class BOARDCOVER {
    // 4가지 타입의 시작 블록
    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}} //┘
    };
    
    // 각각 높이, 넓이,흰칸의 수, 게임판, 경우의 수
    static int H,W, wc, ans;
    static int[][] board;
    
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    
    public static void main(String[] args) throws IOException {
        int C = Integer.parseInt(sc.readLine());
        
        for(int i=0; i<C; i++) {
            st = new StringTokenizer(sc.readLine());
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            
            // 흰색 칸의 수와 보드 초기화
            wc=0;
            board = new int[H][W];
            
            // board판에 흰색과 검은색을 채워 넣는 과정
            for(int y=0; y<H; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<W; x++) {
                    String tmp = st.nextToken();
                    
                    // 흰색 칸은 0, 검은색 칸은 1
                    board[y][x] = tmp.equals(".") ? 0:1;
                    
                    if(board[y][x]==0) {
                        wc++;
                    }
                }
            }
            
            // solve()를 호출하는 과정
            // 3의 배수라면 호출
            // 아니면 0 출력
            ans=0;
            if(wc%3==0) {
                solve(wc);
            }
            sb.append(ans+"\n");
        }
        System.out.println(sb);
    }
    
    // 모든 경우의 수를 구해보는 핵심 메서드
    static void solve(int WC) {
        
        
 // 기저사례(1): 하나의 경우의 수를 찾은 경우

        if(WC==0) { 
            ans++;
            return;
        }
        
        for(int y=0; y<H; y++) {
            for(int x=0; x<W; x++) {
                if(board[y][x]==0) {
                    for(int k=0; k<4; k++) {
                        if(check(k, y, x)) {
                            set(k, y, x, 1);
                            solve(WC-3);
                            set(k,y,x,0);
                        }
                    }
                    return;
                }
            }
        }
    }
    
    // coverType 4가지가 보드판에 맞는지 확인하는 메서드
    static boolean check(int k, int y, int x) {
        for(int i=0; i<3; i++) {
            int ny = y + coverType[k][i][0];
            int nx = x + coverType[k][i][1];
            
            if(!inRange(ny, nx) || board[ny][nx]==1) {
                return false;
            }
        }
        return true;
    }
    
    // 보드판 범위에 포함하는 지 확인하는 메서드
    static boolean inRange(int ny, int nx) {
        return (ny>=0 && ny<H) && (nx>=0 && nx<W);
    }
    
    // 보드판에 흰색(0) 또는 검은색(1)으로 설정하는 메서드
    static void set(int k, int y, int x, int c) {
        for(int i=0; i<3; i++) {
            int ny = y + coverType[k][i][0];
            int nx = x + coverType[k][i][1];
            board[ny][nx] = c;
        }
    }
}