[알고스팟] 게임판 덮기 :: 늦깎이 IT

[알고스팟 게임판 덮기 링크]

1. L자 모양의 블럭으로 게임판을 덮는 경우의 수를 구하는 문제인데, 이는 L자 모양의 블럭으로 게임판을

덮는 순서와는 상관이 없다. 즉, 순서가 어떻게 되든지간에 게임판을 덮는 모양이 같다면 하나의 경우로 취급한다.

2. 맨 위쪽, 맨 왼쪽부터 게임판이 덮이지 않은 위치를 찾는다. 그리고 그 위치에서 부터 L자 모양의 블럭을 놓는다.

 - 여기서, 이전의 칸들은 이미 블럭이 덮여있다고 가정해야한다. 즉, L자 모양의 블럭을 해당 위치에 놓을 때,

아래쪽 혹은 오른쪽으로만 뻗어나가게 해야한다.

 - 소스 코드에서, coverDir[][][] 배열을 참고하기 바란다.

3. 해당 위치에서, L자 모양의 블럭을 둘 수 있는지 없는지를 따로 확인하지 않는다. Map의 범위를 벗어나지 않는

이상, 검은색 타일이 있는 곳에도 우선 L자 블럭을 놓는다. L자 블럭을 놓는 행위는 Map의 해당 위치에 +1을 한다.

그 후, 해당 위치의 값이 1보다 크다면, 검은 타일과 겹쳤거나, 또 다른 L자 블럭과 겹쳤다는 뜻이므로 false를

리턴한다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int C, H, W, ans;
    public static int[][] map;
    public static boolean[] visited;
    public static int[] dirX = new int[] { 0, 0, 1, -1 }; // 동서남북
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static int[][][] coverDir = new int[][][] { { { 0, 0 }, { 1, 0 }, { 1, -1 } },
            { { 0, 0 }, { 1, 0 }, { 1, 1 } }, { { 0, 0 }, { 1, 0 }, { 0, 1 } }, { { 0, 0 }, { 0, 1 }, { 1, 1 } } };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
 
        for (int t = 1; t <= C; t++) {
 
            st = new StringTokenizer(br.readLine());
            H = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
 
            ans = 0;
            map = new int[H][W];
 
            int cnt = 0;
            for (int i = 0; i < H; i++) {
                String str = br.readLine();
                for (int j = 0; j < W; j++) {
                    char ch = str.charAt(j);
                    if (ch == '#')
                        map[i][j] = 1; // 검은색 타일
                    else
                        cnt += 1;
                }
            }
 
            if (cnt % 3 != 0)
                System.out.println(0);
            else {
                dfs(0, cnt / 3);
                System.out.println(ans);
            }
        }
    }
 
    public static boolean setBlock(int row, int col, int type, int val) {
 
        boolean flag = true;
 
        for (int i = 0; i < 3; i++) {
 
            int nr = row + coverDir[type][i][0];
            int nc = col + coverDir[type][i][1];
 
            if (isBoundary(nr, nc)) {
                map[nr][nc] += val;
                if (map[nr][nc] > 1)
                    flag = false;
            } else {
                flag = false;
            }
        }
        return flag;
    }
 
    public static void dfs(int count, int numOfBlock) {
 
        if (count == numOfBlock) {
            ans += 1;
            return;
        }
 
        for (int i = 0; i < H; i++) {
 
            boolean flag = true;
 
            for (int j = 0; j < W; j++) {
 
                if (map[i][j] == 0) {
 
                    for (int type = 0; type < 4; type++) {
                        if (setBlock(i, j, type, 1))
                            dfs(count + 1, numOfBlock);
                        setBlock(i, j, type, -1);
                    }
                    flag = false;
                    break;
                }
            }
            if (!flag)
                break;
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < H) && (col >= 0 && col < W);
    }
 
    public static void showMap(int[][] map) {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}