[BOARDCOVER] 게임판 덮기

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

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

algospot.com :: BOARDCOVER

풀이입니다. 🤔

import java.util.Scanner;
 
public class Main {
    private static final char WHITE = '.';
    private static final char USE = '^';
    /**
     * index 가 빠른 순서를 기준으로 탐색하기 위한 상태좌표 (y, x)
     * 칸을 덮는 부분에 대해 코드로 구현하는 것이 아닌, 데이터로 나타내는 것이 중요하다.
     *
     * (1) **  (2) *   (3) **  (4)  *
     *      *      **      *       **
     */
    private static final int[][][] coverTypes = {
            {{0, 0}, {0, 1}, {1, 1}}, // (1)
            {{0, 0}, {1, 0}, {1, 1}}, // (2)
            {{0, 0}, {1, 0}, {0, 1}}, // (3)
            {{0, 0}, {1, -1}, {1, 0}} // (4)
    };
    private static final char[][] boards = new char[20][20];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int h = scanner.nextInt();
            int w = scanner.nextInt();
            for (int i = 0; i < h; ++i) {
                String line = scanner.next();
                for (int j = 0, len = line.length(); j < len; ++j) {
                    boards[i][j] =  line.charAt(j);
                }
            }
 
            System.out.println(getCount(h, w));
        }
    }
 
    private static int getCount(int h, int w) {
        Coordinate start = getStart(h, w);
        if (start == null) {
            // 기저사례 : 시작할 좌표가 없다면, 모든 보드가 채워졌음.
            return 1;
        }
 
        int ret = 0;
        for (int type = 0; type < 4; ++type) {
            if (isCoverall(h, w, start.y, start.x, type)) {
                cover(start.y, start.x, type, true);
                ret += getCount(h, w);
                cover(start.y, start.x, type, false);
            }
        }
 
        return ret;
    }
 
    private static Coordinate getStart(int h, int w) {
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (boards[i][j] == WHITE) return new Coordinate(i, j);
            }
        }
        return null;
    }
 
    private static boolean isCoverall(int h, int w, int y, int x, int type) {
        for (int i = 0; i < 3; ++i) {
            int targetY = y + coverTypes[type][i][0], targetX = x + coverTypes[type][i][1];
            if (targetY < 0 || targetY >= h) return false;
            if (targetX < 0 || targetX >= w) return false;
            if (boards[targetY][targetX] != WHITE) return false;
        }
 
        return true;
    }
 
    private static void cover(int y, int x, int type, boolean isCover) {
        for (int i = 0; i < 3; ++i) {
            boards[y + coverTypes[type][i][0]][x + coverTypes[type][i][1]] = isCover ? USE : WHITE;
        }
    }
 
    private static final class Coordinate {
        final int y, x;
 
        public Coordinate(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

이 풀이는 기존에 풀었던 아래 문제와 유사합니다. 

 

[PICNIC] 피크닉

재귀로 완전 탐색을 하되, 중복 케이스를 세는 것을 방지하기 위해 사전 순을 기준으로 조회하도록 하였습니다.

이번 문제에서 한번 더 주의 깊게 살펴볼 내용은 게임판을 덮는 케이스 4 가지를 배열로 선언했다는 점인데요. 
처음 문제를 풀었을 때는 게임판을 덮는 방법을 코드로 제작하였는데, 각 방법의 변하는 부분인 상대좌표를 배열로 나타낸다면 조금 더 보기 쉬운 코드가 만들어질 수 있음을 알게 되었습니다.

int[][][] coverTypes = {
    {{0, 0}, {0, 1}, {1, 1}}, // (1)
    {{0, 0}, {1, 0}, {1, 1}}, // (2)
    {{0, 0}, {1, 0}, {0, 1}}, // (3)
    {{0, 0}, {1, -1}, {1, 0}} // (4)
};

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️