[BOARDCOVER] 게임판 덮기
개발이야기/알고스팟2021. 12. 28. 23:29
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 = {
{{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;
}
}
}
|
cs |
이 풀이는 기존에 풀었던 아래 문제와 유사합니다.
[PICNIC] 피크닉
재귀로 완전 탐색을 하되, 중복 케이스를 세는 것을 방지하기 위해 사전 순을 기준으로 조회하도록 하였습니다.
이번 문제에서 한번 더 주의 깊게 살펴볼 내용은 게임판을 덮는 케이스 4 가지를 배열로 선언했다는 점인데요.
처음 문제를 풀었을 때는 게임판을 덮는 방법을 코드로 제작하였는데, 각 방법의 변하는 부분인 상대좌표를 배열로 나타낸다면 조금 더 보기 쉬운 코드가 만들어질 수 있음을 알게 되었습니다.
|
1
2
3
4
5
6
|
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)
};
|
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 |