1. 문제 설명
(1) 게임판 덮기 문제는 아래와 같은 게임판을 이용하여 삼각형( ┌, ┐, └, ┘)을 가지고 흰색 칸에 빈틈없이
채울 수 있는 최대 경우의 수를 구하는 것이다.
( 이때, 검은색 칸에는 채울 수 없으며 연속으로 이어져 있다. )
2. 입출력 조건 및 예제
입력 조건
(1) 첫 번째 줄에는 문제 입력 수 C를 입력받는다.
(2) 두 번째 줄부터는 게임판의 높이 H와 넓이 W를 입력받는다.
( H>=1과 W<=20 )
(3) 그 이후 세번째 줄부터는 게임판 크기만큼 흰색과 검은색을 채운다.
( 여기서는 #이 검은색 .이 흰색 )
(3) 게임판에 있는 흰칸의 수는 50을 넘지 않아야 한다.
(4) 흰 칸에 채워질 도형의 크기는 3칸이므로, 반드시 흰칸의 수는 3배수 이어야 한다.
출력 조건
(1) 흰색 칸에 채울 수 있는 최대 경우의 수를 출력한다.
입력 예제
3
3 7
# . . . . . #
# . . . . . #
# # . . . # #
3 7
# . . . . . #
# . . . . . #
# # . . # # #
8 10
# # # # # # # # # #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# . . . . . . . . #
# # # # # # # # # # |
출력 예제
0
2
1514
|
3. 풀이 및 코드
: 이 유형의 문제는 항상 특정 순서를 세워서 풀어야 한다.
바로 가장 왼쪽 상단부터 시작하여 삼각형( ┌, ┐, └, ┘)을 가지고 하나씩 채우면서 재귀 호출 하는 것이다.
또한 삼각형( ┌, ┐, └, ┘)은 아래의 표처럼 (0,0) 기준으로 잡고 범위를 체크한다.
-1 | 0 | 1 | |
-1 | (-1,-1) | (-1,0) | (-1,1) |
0 | (0,-1) | (0,0) | (0,1) |
1 | (1,-1) | (1,0) | (1,1) |
또한 삼각형을 넣을때마다 게임판 범위 안에 드는 것인지 흰색과 검은색을 구분하고 삼격형을 넣는 것인지 항상 체크해야
한다.
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
public class BOARDCOVER {
// 4가지 타입의 시작 블록
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}} //┘
};
// 각각 높이, 넓이,흰칸의 수, 게임판, 경우의 수
static int H,W, wc, ans;
static int[][] board;
static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
public static void main(String[] args) throws IOException {
int C = Integer.parseInt(sc.readLine());
for(int i=0; i<C; i++) {
st = new StringTokenizer(sc.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
// 흰색 칸의 수와 보드 초기화
wc=0;
board = new int[H][W];
// board판에 흰색과 검은색을 채워 넣는 과정
for(int y=0; y<H; y++) {
st = new StringTokenizer(sc.readLine());
for(int x=0; x<W; x++) {
String tmp = st.nextToken();
// 흰색 칸은 0, 검은색 칸은 1
board[y][x] = tmp.equals(".") ? 0:1;
if(board[y][x]==0) {
wc++;
}
}
}
// solve()를 호출하는 과정
// 3의 배수라면 호출
// 아니면 0 출력
ans=0;
if(wc%3==0) {
solve(wc);
}
sb.append(ans+"\n");
}
System.out.println(sb);
}
// 모든 경우의 수를 구해보는 핵심 메서드
static void solve(int WC) {
// 기저사례(1): 하나의 경우의 수를 찾은 경우
if(WC==0) {
ans++;
return;
}
for(int y=0; y<H; y++) {
for(int x=0; x<W; x++) {
if(board[y][x]==0) {
for(int k=0; k<4; k++) {
if(check(k, y, x)) {
set(k, y, x, 1);
solve(WC-3);
set(k,y,x,0);
}
}
return;
}
}
}
}
// coverType 4가지가 보드판에 맞는지 확인하는 메서드
static boolean check(int k, int y, int x) {
for(int i=0; i<3; i++) {
int ny = y + coverType[k][i][0];
int nx = x + coverType[k][i][1];
if(!inRange(ny, nx) || board[ny][nx]==1) {
return false;
}
}
return true;
}
// 보드판 범위에 포함하는 지 확인하는 메서드
static boolean inRange(int ny, int nx) {
return (ny>=0 && ny<H) && (nx>=0 && nx<W);
}
// 보드판에 흰색(0) 또는 검은색(1)으로 설정하는 메서드
static void set(int k, int y, int x, int c) {
for(int i=0; i<3; i++) {
int ny = y + coverType[k][i][0];
int nx = x + coverType[k][i][1];
board[ny][nx] = c;
}
}
}
|
cs |
'알고리즘 (with JAVA) > 완전 탐색' 카테고리의 다른 글
시계 맞추기 (골드1) (0) | 2022.08.31 |
---|---|
외판원 문제(TSP, 실버1) (0) | 2022.08.30 |
소풍 문제 (0) | 2022.08.29 |
보글 게임 (골드2) (0) | 2022.08.29 |
n개의 원소 중 m개를 고르는 순열과 조합 (0) | 2022.08.29 |