반응형
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
|
package test;
import java.util.Scanner;
public class test{
public static void main(String[] args) {
int board[][];
Scanner scanner = new Scanner(System.in);
int test = scanner.nextInt();
for(int i = 0; i < test; i++) {
int y = scanner.nextInt();
int x = scanner.nextInt();
board = new int[y][x];
for(int j = 0; j < y; j++) {
String str = scanner.next();
for(int k = 0; k < x; k ++) {
board[j][k] = (str.charAt(k) == '#')? 1:0;
}
}
String result = ""; result += (i+1 == test) ? cover(board): cover(board)+"\n";
}
}
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} }
};
private static boolean set(int[][] board, int y, int x, int type, int delta) {
boolean ok = true;
/* y, x좌표를 기준으로 type에 따라 블럭을 위치시킨다. 아래의 if문 2개로 올바르지 않다면 false를 반환한다. */ for(int i = 0; i < 3; i++) {
int ny = y + coverType[type][i][0];
int nx = x + coverType[type][i][1];
// 위치가 지도를 넘어가지 않는지 검사하는 조건문
if(ny < 0 || ny >= board.length || nx < 0 || nx >= board[0].length) ok = false;
/* 좌표에 1을 추가하여 겹치는지 아닌지를 확인해 본다. delta가 -1일때는 원래 있던 블럭을 치우는 역할을 한다. */ else if((board[ny][nx] += delta) > 1)
ok = false;
}
return ok;
}
private static int cover(int[][] board) {
int y = -1, x = -1;
// 비어있는 좌표를 찾는 2중 반복문이다. for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
if(board[i][j] == 0) {
y = i;
x = j;
break;
}
}
if(y != -1)
break;
}
//비어있는 공간이 없으면 1을 리턴한다. if(y == -1)
return 1;
int ret = 0;
for(int type = 0; type < 4; type ++) {
//set 함수를 실행하여 블럭이 정상적으로 채워지면 재귀호출로 다음블럭을 놓는다. if(set(board, y, x, type, 1))
ret += cover(board);
/* if문에서 조건확인을 위해 set함수를 실행시켰기 때문에 블럭을 올릴 위치에 +1했던값을 다시 -1을 해줌으로서 원래 블럭을 올리기 전의 모습으로 돌아간다. */ set(board, y, x, type, -1);
}
return ret;
}
}
|
cs |
반응형
'알고리즘 > 알고리즘 문제해결전략' 카테고리의 다른 글
예제 : 수열의 빠른 합 (0) | 2020.11.23 |
---|---|
문제 ID : CLOCKSYNC, 난이도: 중 (0) | 2020.11.23 |
예제 : 여행하는 외판원 (0) | 2020.11.09 |
문제 ID : PICNIC, 난이도: 하 (0) | 2020.11.02 |