[Java] 백준(골드-4) 14500번 - 테트로미노
문제 풀이
이번 문제는 완전탐색을 이용하는데 DFS를 곁들여 풀 수 있는 문제이다.
아이디어 도출
이 문제는 주어진 배열을 완전 탐색하는데, 5가지 테트로미노를 잘 고려해야 한다.
먼저 4가지 테트로미노를 보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ㅁㅁㅁㅁ
1234
ㅁ
ㅁ
ㅁㅁ
1
2
34
ㅁ
ㅁㅁ
ㅁ
1
23
4
ㅁㅁ
ㅁㅁ
14
23
위 테트로미노들은 상하좌우로 완전탐색하면 4번만큼 탐색하며 만들 수 있다는 것을 알 수 있다. 이는 회전한 형태도 구할 수 있다는 것이다.
1
2
3
4
5
6
ㅁ
ㅁㅁ
ㅁ
1
23
4
문제는 위 테트로미노이다. 위와 같이 탐색의 2번째 칸에서 오른쪽과 밑쪽인 양쪽으로 하나씩 움직여야 만들 수 있는 형태이다. 그래서 상하좌우 4칸 탐색만으로는 만들 수 없다. 그래서 탐색할 때 2번째 칸에서 다시 한번 더 탐색하는 경우의 수를 추가해주면 된다.
이를 위한 아이디어는 다음과 같다.
- 지도에서 상,하,좌,우로 4칸씩 완전 탐색하면서 깊이가 4가 될 때까지 DFS 재귀 호출한다.
- 단, 2번째 칸(깊이)일 때, ㅗ,ㅓ,ㅏ,ㅜ 형태를 띄는 테트로미노를 놓기 위해 한 번 더 DFS 재귀호출하여 양쪽으로 움직이는 경우의 수를 추가한다.
- 깊이가 4가 되면 테트로미노를 놓은 것이기에 이때의 지도 위치 합계 중 최대값을 구한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
import java.io.*;
import java.util.*;
class Main {
// 상,하,좌,우로 움직이기 위한 배열
static int[] dx = new int[]{1, 0, -1, 0};
static int[] dy = new int[]{0, 1, 0, -1};
// 방문 배열 선언
static boolean[][] visited;
// 입력 배열 선언
static int[][] arr;
// 입력 배열의 크기 NxM 선언
static int N, M;
// 테트로미노를 놓았을 때 최대값을 담을 변수 선언
static int max;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][M];
visited = new boolean[N][M];
// 지도에 테트로미노를 놓았을 때 최대값을 갱신할 변수 초기화
max = Integer.MIN_VALUE;
// 지도 입력
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// 지도의 전체 탐색을 진행한다.
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
// 모든 위치에서 DFS를 호출한다.
visited[i][j] = true;
DFS(i, j, arr[i][j], 1);
visited[i][j] = false;
}
}
// 갱신된 최대 합계 값 출력
bw.write(max+"\n");
bw.close();
br.close();
}
static void DFS(int x, int y, int sum, int depth) {
// 테트로미노는 4칸으로 이루어졌기에 4칸까지 탐색하고 점수 총합 계산 후 종료
if(depth == 4) {
max = Math.max(max, sum);
return;
}
// 상,하,좌,우로 탐색하며 테트로미노(4칸)만큼 탐색한다.
for(int dir=0; dir<4; dir++) {
int i = x + dx[dir];
int j = y + dy[dir];
// 배열의 범위를 벗어나는지 확인
if(isRange(i, j)) {
// 방문하지 않은 위치라면
if(!visited[i][j]) {
// 보라색(ㅗ,ㅏ,ㅓ,ㅜ) 테트로미노를 만들기 위해 2번째 탐색 위치에서 한번 더 탐색을 진행한다.
if(depth == 2) {
visited[i][j] = true;
DFS(x, y, arr[i][j]+sum, depth+1);
visited[i][j] = false;
}
// 탐색을 진행한다.
visited[i][j] = true;
DFS(i, j, arr[i][j]+sum, depth+1);
visited[i][j] = false;
}
}
}
}
static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<N && y<M) {
return true;
}
return false;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.