게임판 덮기 (ID : BOARDCOVER)

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

algospot.com :: BOARDCOVER

 

 

문제를 풀려고 고민을 꽤 오래했지만 결국 풀지못하고 답안 코드를 봤다.

 

알고 스팟에 답안 제출한 코드는 아래와 같다.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public 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) {
        Scanner scanner = new Scanner(System.in);

        int caseCount = Integer.parseInt(scanner.nextLine());
        for (int cc = 0; cc < caseCount; cc++) {
            int h, w;
            List<List<Integer>> board = new ArrayList<>();

            String[] hw = scanner.nextLine().trim().split(" ");
            h = Integer.parseInt(hw[0]);
            w = Integer.parseInt(hw[1]);

            for (int r = 0; r < h; r++) {
                String row = scanner.nextLine();
                List<Integer> rowList = new ArrayList<>();
                for (int c = 0; c < w; c++) {
                    if(row.charAt(c) == '#') {
                        rowList.add(1);
                    } else {
                        rowList.add(0);
                    }
                }
                board.add(rowList);
            }

            System.out.println(cover(board));
        }
    }

    public static boolean set(List<List<Integer>> board, int row, int col, int type, int delta) {
        boolean ok = true;
        for (int i = 0; i < 3; i++) {
            int nrow = row + coverType[type][i][0];
            int ncol = col + coverType[type][i][1];
            if (nrow < 0 || nrow >= board.size() || ncol < 0 || ncol >= board.get(0).size()) {
                ok = false;
            } else {
                board.get(nrow).set(ncol, board.get(nrow).get(ncol) + delta);
                if (board.get(nrow).get(ncol) > 1) {
                    ok = false;
                }
            }
        }
        return ok;
    }

    public static int cover(List<List<Integer>> board) {
        // 아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
        int row = -1, col = -1;
        for (int r = 0; r < board.size(); r++) {
            for (int c = 0; c < board.get(0).size(); c++) {
                if (board.get(r).get(c) == 0) {
                    row = r;
                    col = c;
                    break;
                }
            }
            if (row != -1) {
                break;
            }
        }

        // 기저 사례: 모든 칸을 채웠으면 1을 반환한다.
        if (row == -1) {
            return 1;
        }

        int result = 0;
        for (int type = 0; type < 4; type++) {
            if (set(board, row, col, type, 1)) {
                result += cover(board);
            }
            set(board, row, col, type, -1);
        }

        return result;
    }
}