[Java] 백준(골드-4) 14502번 - 연구소
문제 풀이
이번 문제는 그래프 탐색 기법인 DFS와 BFS 모두를 활용한다면 풀 수 있는 문제이다.
아이디어 도출
먼저 DFS와 BFS를 어떻게 활용할 수 있을까를 보면 다음과 같다.
- 주어지는 연구소 배열에서 3개의 벽을 세우는 모든 경우의 수를 구하기 위해 DFS를 활용.
- 3개의 벽이 세워진 후, 바이러스를 퍼뜨리기 위해 BFS를 활용.
DFS를 통해 연구소 배열 원본에서 벽을 3개씩 세운 후 BFS를 호출하여 바이러스를 퍼뜨리게 된다. 이때, 모든 경우의 수마다 바이러스를 퍼뜨려야 하기 때문에 원본 배열을 변경하지 않고 BFS가 호출될 때마다 원본배열을 복사한 배열에서 바이러스를 퍼뜨려야 한다.
여기서 주의할 점은 원본 배열을 복사하는 복사 배열을 만들 때, 얕은 복사가 아닌 깊은 복사를 사용해야 한다는 것이다.
copyMap = OrgMap과 같은 대입연산자를 이용해 얕은 복사를 한다면 원본 배열 값에 영향이 있기 때문에 깊은 복사를 사용해야 한다.
그래서 구체적인 문제 해결 과정을 다음과 같이 도출하였다.
- 연구소 배열에서 DFS를 통해 3개의 벽을 세울 때, 벽을 세울 수 있는 영역인지 확인 후 벽을 세운다.
- 3개의 벽을 세운 후, BFS가 호출된다면 바이러스인 2를 기준으로 상하좌우로 퍼뜨린다. 이때 깊은 복사를 통한 복사배열에 바이러스를 퍼뜨린다.
- 바이러스를 모두 퍼뜨린 후, 복사배열을 순회하며 안전영역의 크기를 센다.
- 안전 영역의 최대 크기를 출력한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
import java.io.*;
import java.util.*;
class Main {
// 상하좌우를 탐색하기 위한 dx, dy 배열 선언
static int[] dx = new int[]{0, 1, 0, -1};
static int[] dy = new int[]{1, 0, -1, 0};
// 연구소 원본배열과 복사해서 사용할 복사배열
static int[][] map;
// 연구소 배열의 크기를 담을 변수 N과 M
static int N;
static int M;
// 안전영역의 최댓값을 담을 변수
static int safeZoneMaxCnt = 0;
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());
map = new int[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 1. DFS를 통해 3개의 벽을 세우는 모든 경우의 수를 구한다.
// 2. 벽을 3개 세울 때마다 BFS를 통해 바이러스를 퍼뜨려 안전영역의 크기를 구한다.
// 3. 마지막으로 구하는 안전영역의 크기가 가장 큰 경우를 구하면 된다.
DFS(0);
bw.write(safeZoneMaxCnt + "\n");
bw.close();
br.close();
}
/**
* DFS 재귀함수
* map 배열에 벽 3개를 새로 세우는 모든 경우의 수를 구한다.
* 3개의 벽을 세울 때마다 BFS 함수를 호출한다.
*/
static void DFS(int wall) {
if(wall == 3) {
BFS();
return;
}
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == 0) {
map[i][j] = 1;
DFS(wall + 1);
map[i][j] = 0;
}
}
}
}
/**
* BFS 함수
* 3개의 벽이 세워진 연구소 배열에서 2를 기준으로 바이러스를 퍼뜨린다.
* 바이러스를 모두 퍼뜨린후, 0의 개수, 즉 안전영역의 크기를 구한다.
*/
static void BFS() {
Queue<int[]> q = new LinkedList<>();
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == 2) {
q.add(new int[]{i, j});
}
}
}
int[][] copy_map = new int[N][M];
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
copy_map[i][j] = map[i][j];
}
}
while(!q.isEmpty()) {
int[] now = q.poll();
for(int dir=0; dir<4; dir++) {
int i = now[0] + dx[dir];
int j = now[1] + dy[dir];
if(isRange(i, j)) {
if(copy_map[i][j] == 0) {
copy_map[i][j] = 2;
q.add(new int[]{i, j});
}
}
}
}
safeZoneMaxCnt = Math.max(safeZoneMaxCnt, countSafeZone(copy_map));
}
static int countSafeZone(int[][] virusMap) {
int safeZoneCnt = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(virusMap[i][j] == 0) {
safeZoneCnt++;
}
}
}
return safeZoneCnt;
}
static boolean isRange(int x, int y) {
if(0<=x && 0<=y && x<N && y<M) {
return true;
}
return false;
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.