백준 14502번 : 연구소
이 문제는 n*m 크기의 직사각형 그래프에서 각각
0 = 빈 칸
1 = 벽
2 = 바이러스
라 가정하고 0에 1을 세 개를 사용해 바이러스가 퍼지는 것을 막는 경우의 수를 파악하여 0의 최대 개수를 구하는 문제이다.
이 때, 바이러스는 상하좌우 인접한 0으로 퍼진다.
1
2
3
4
5
6
7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
이러한 그래프가 연구소의 지도라고 가정한다면 각각 좌우에 바이러스인 2가 배치 되어 있으므로 이를 벽인 1을 세 개 사용해 막는다면 다음과 같아진다.
1
2
3
4
5
6
7
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
각각 1을 3개 사용해 0 전체에 바이러스가 퍼지는 것을 막았으며 시간이 경과해 바이러스가 퍼지게 된다면 다음과 같아진다.
1
2
3
4
5
6
7
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
여기까지 도달한 후 더 이상 바이러스인 2가 퍼지지 않는 0을 안전 구역이라 하며, 현재 예시의 최종 안전 구역의 크기는 27이다.
우선 알고리즘의 전체적인 흐름은
- 빈 칸 3개의 벽을 세울 수 있는 모든 경우의 수를 구한다. (브루트포스 알고리즘)
- 벽 3개를 세운 뒤, 바이러스가 퍼지는 상황을 시뮬레이션한다. (탐색 알고리즘)
- 바이러스가 퍼진 다음 빈 칸의 개수를 세어 최댓값을 업데이트한다. (결과값 연산)
세 단계로 구분 될 수 있다.
이를 위해
- 벽을 세우는 경우의 수를 구하는 함수
- 바이러스 시뮬레이션 함수
- 안전 영역 크기를 세는 함수
세 함수로 나누어 문제를 풀었다.
가장 먼저 각 함수에서 공통적으로 필요한 변수를 클래스 멤버 변수로 선언했다.
1
2
3
4
public class Main {
static int[][] arr, copy;
static int n, m;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
각각 arr은 연구소, copy는 연구소 지도를 바탕으로 시뮬레이션 결과를 표현할 배열이고, n과 m은 문제에서 주어지는 연구소의 가로, 세로 크기이다.
또한, 바이러스가 상하좌우로 퍼질 수 있기 때문에 탐색 실행 시에 해당 방향으로 이동할 수 있어야한다.
그렇기 때문에 방향을 지정하는 배열을 선언, 초기화 했다.
다음으로는 그래프 문제를 풀기 위해 그래프를 표현했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
copy = new int[n][m];
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());
}
}
System.out.println(wall(0));
n과 m을 입력 받아 연구소와 시뮬레이션 결과 배열의 크기를 지정해주었고, 이중 반복문을 실행해 그 다음으로 입력 받는 연구소 지도를 그대로 표현했다.
이후, 바로 연산을 시작하고 출력하게 되는데 자세한 내용은 세 단계의 함수로 나누어 볼 것이다.
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
public static int wall(int count) {
int maxArea = 0; // 1
if (count == 3) { // 2
for (int i = 0; i < n; i++) { // 2-1
System.arraycopy(arr[i], 0, copy[i], 0, m);
}
for (int i = 0; i < n; i++) { // 2-2
for (int j = 0; j < m; j++) {
if (copy[i][j] == 2) {
// virusDFS(i, j);
virusBFS(i, j); // 2-3
}
}
}
return countSafeZone(); // 2-4
}
for (int i = 0; i < n; i++) { // 3
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) { // 3-1
arr[i][j] = 1; // 3-2
maxArea = Math.max(maxArea, wall(count + 1)); // 3-3, 3-5
arr[i][j] = 0; // 3-4
}
}
}
return maxArea; // 4
}
이 함수는 재귀적으로 벽을 세우는 모든 경우를 탐색하고서 벽을 세운 후의 안전 구역의 최댓값을 반환한다.
흐름은 다음과 같다.
- maxArea를 안전 구역 최댓값을 저장하는 변수로 사용한다.
- if count = 3 은 벽을 3개 다 세운 경우이다. (엣지케이스)
- 이 경우 연구소 arr을 복사한 시뮬레이션 용 배열인 copy 배열을 생성한다.
- 모든 위치를 순회하면서 바이러스가 있는 위치를 찾는다.
- 바이러스가 있는 위치에서 BFS 혹은 DFS로 구현된 바이러스를 퍼뜨리는 함수를 실행시킨다.
- 바이러스가 전부 퍼진 후에는 countSafeZone() 함수를 호출하여 안전 구역의 크기를 계산하고, 이 값을 반환한다.
- 벽을 아직 3개 다 세우지 못한 경우에는
- 모든 위치를 순회하면서 빈 칸을 찾는다.
- 빈 칸에 벽을 세우고
- 벽을 하나 더 세운 상태에서의 안전 구역 최댓값을 계산한다. (재귀)
- 계산 후에 세웠던 벽을 제거하여 다른 경우를 탐색할 수 있게 한다.
- 이 과정을 거쳐 벽을 세울 수 있는 모든 위치에 대한 안전 구역의 최댓값을 계산하고, 이 중 최대인 값을 구한다.
- 마지막으로 벽을 세울 수 있는 모든 경우를 탐색한 후, 안전 구역의 최댓값을 반환한다.
복잡한 로직인 만큼 주석으로 어느 설명에 해당하는 지 표시해 두었다.
이 문제에서 현재 함수 부분이 가장 어려우며 다음으로 작성할 탐색이나 안전 구역 총계 계산 함수는 크게 어렵지 않다.
이번에는 탐색 부분인데, 바이러스를 퍼뜨리는 역할을 하는 함수이기 때문에 방문한 곳의 값을 2로 바꾸는 것 외에는 이전에 활용했던 2차원 탐색 알고리즘들과 크게 다른 점은 없다.
1. BFS 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void virusBFS(int x, int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while(!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (copy[nx][ny] == 0) {
copy[nx][ny] = 2;
q.offer(new int[]{nx, ny});
}
}
}
}
}
우선은 문제 자체가 BFS 카테고리이기 때문에 BFS를 먼저 작성한다.
항상 보던 그 맛이다.
시작 좌표를 큐에 넣고 상하좌우 반복하며 조건에 맞을 때마다 다음 위치로 옮겨가는 로직이다.
다만 바이러스가 퍼지는 것인 만큼 두 가지는 조건을 유의해야한다.
- 바이러스는 인접한 빈칸으로 퍼질 수 있다.
- 다시 말해, 인접한 빈칸인 0으로만 이동 가능하다.
- 바이러스가 지나가면 해당 위치는 0에서 2로 변경된다.
- 즉, 해당 좌표의 값을 2로 초기화 해야한다.
이 두 가지만 조심한다면 기존 탐색 알고리즘 사용법과 동일하다.
2. DFS 탐색
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void virusDFS(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (copy[nx][ny] == 0) {
copy[nx][ny] = 2;
virusDFS(nx, ny);
}
}
}
}
BFS 탐색의 주의사항과 같다.
다음 좌표의 값이 0일 때만 이동할 수 있으며, 이동했다면 해당 자리는 2로 초기화시킨다.
BFS 탐색과 마찬가지로 visited 배열을 따로 사용할 필요 없을 뿐 이전에 알아보았던 BFS 탐색 방식과 동일하다.
마지막으로 countSafeZone 함수인데, 이 함수는 단순히 시뮬레이션 결과 배열 내의 0의 개수를 세어주는 함수이기 때문에 따로 설명이 필요할 것이라 생각치 않는다.
1
2
3
4
5
6
7
8
9
10
11
public static int countSafeZone() {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (copy[i][j] == 0) {
count++;
}
}
}
return count;
}
전체 소스코드는 다음과 같다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] arr, copy;
static int n, m;
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
copy = new int[n][m];
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());
}
}
System.out.println(wall(0));
}
public static int wall(int count) {
int maxArea = 0;
if (count == 3) {
for (int i = 0; i < n; i++) {
System.arraycopy(arr[i], 0, copy[i], 0, m);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (copy[i][j] == 2) {
// virusDFS(i, j);
virusBFS(i, j);
}
}
}
return countSafeZone();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
maxArea = Math.max(maxArea, wall(count + 1));
arr[i][j] = 0;
}
}
}
return maxArea;
}
public static void virusDFS(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (copy[nx][ny] == 0) {
copy[nx][ny] = 2;
virusDFS(nx, ny);
}
}
}
}
public static void virusBFS(int x, int y) {
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while(!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 4; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (copy[nx][ny] == 0) {
copy[nx][ny] = 2;
q.offer(new int[]{nx, ny});
}
}
}
}
}
public static int countSafeZone() {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (copy[i][j] == 0) {
count++;
}
}
}
return count;
}
}
참고로 위 제출 결과 사진에서 확인할 수 있듯이
나는 항상 DFS, BFS 두 가지 다 활용할 수 있는 경우에는 따로 ns로 시간을 출력해 이 문제에서는 어떤 알고리즘이 더 빠를까를 확인해보는데, 이번 문제에서는 DFS가 훨씬 빨랐다.
테스트 케이스 중 확인할 수 있는 가장 큰 그래프를 탐색할 때
BFS : 429298000 이상의 ns가 걸렸고
DFS : 205794600 이상의 ns가 걸렸다. 거의 2배의 시간 차이를 보인다.
또한 재출 시에 BFS : 303312 KB의 메모리를 사용했고, DFS : 20284 KB의 메모리를 사용했다.
이 문제에서는 벽을 3개 세울 수 있는 모든 경우를 탐색해야하기 때문에 가능한 한 깊게 탐색하는 DFS는 벽을 3개 세운 다음 바로 시뮬레이션을 진행할 수 있지만, 너비 우선으로 탐색하는 BFS는 벽을 세개 세우는 데 시간이 더 오래 걸리기 때문에 차이가 있는 것이다.
또한, 메모리에 대한 차이에서는 DFS는 재귀 호출 시 스택의 크기 만큼만 메모리를 사용하지만, BFS는 모든 노드를 큐에 저장하기 때문에 해당 연산 과정을 거칠 때마다 메모리를 사용하게 된다.
그렇기 때문에 이 문제에 한해서는 BFS보다 DFS 탐색이 더 효율적이라 할 수 있다.
왜 이렇게 어렵나 했더니 골드4 수준 문제였다.
근데 정답률이 50% 이상인게 의아하다…
이제 골드 수준으로 진입한 만큼 한 문제 당 시간이 더 오래걸리게 되었으며, 그 만큼 바로 블로깅 해야하기 때문에 풀 수 있는 수가 적어졌다.
아쉽지만 해야할 일이 많다…