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

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

 

algospot.com :: BOARDCOVER

게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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 = {
            {{00}, {01}, {11}}, // (1)
            {{00}, {10}, {11}}, // (2)
            {{00}, {10}, {01}}, // (3)
            {{00}, {1-1}, {10}} // (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;
        }
    }
}
cs


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

 

[PICNIC] 피크닉


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

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

1
2
3
4
5
6
int[][][] coverTypes = {
    {{00}, {01}, {11}}, // (1)
    {{00}, {10}, {11}}, // (2)
    {{00}, {10}, {01}}, // (3)
    {{00}, {1-1}, {10}} // (4)
};
cs



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

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[XHAENEUNG] 째능 교육  (0) 2021.12.29
[URI] URI Decoding  (0) 2021.12.29
[HOTSUMMER] 에어컨을 끈다고 전력난이 해결될까?  (0) 2021.12.27
[CONVERT] Conversions  (0) 2021.12.27
[PICNIC] 소풍  (0) 2021.12.27
Posted by N'