연구소 3

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.25 초 (하단 참고) 512 MB 13337 3607 2123 25.304%

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

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 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

1
2
3
4
5
6
7
* 6 5 4 - - 2
5 6 - 3 - 0 1
4 - - 2 - 1 2
3 - 2 1 2 2 3
2 2 1 0 1 - -
1 - 2 1 2 3 4
0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

1
2
3
4
5
6
7
0 1 2 3 - - 2
1 2 - 3 - 0 1
2 - - 2 - 1 2
3 - 2 1 2 2 3
3 2 1 0 1 - -
4 - 2 1 2 3 4
* - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

풀이

입력으로 주어진 바이러스의 갯수는 M개보다 크거나 같다.

따라서 바이러스의 갯수에서 M개를 골라서 활성화시킬 바이러스를 고른다. 그리고 바이러스를 퍼트린다. 모든 칸에 바이러스를 퍼트릴 수 있다. 이때, 바이러스를 모든 칸에 퍼트리는데 걸리는 최소 시간을 구하는 문제이다.

나의 풀이는 다음과 같다.

  • 바이러스의 위치를 확인하여 리스트에 넣는다.
  • 조합을 통해서 이 리스트에서 m개의 바이러스만 선택한다.
  • m개의 바이러스가 선택되면, 바이러스를 퍼트린다.
  • 퍼트리는 과정은 bfs 탐색을 통해 진행한다.
  • 이를 copy 한 배열에 퍼트림으로써 원본 배열을 유지한다.

하지만, 문제에서 제공하는 테스트 케이스 1과 7만 맞고 나머지는 맞지 않았다.

조합을 통해서 구하는 건 맞는데, 바이러스를 퍼트리고 그 과정에서 활성 바이러스와 비활성 바이러스를 구분하는 부분의 구현이 조금 어려웠다. 그래서 거기서 틀린 것으로 추측된다.

처음 접근한 나의 코드는 다음과 같다.
[나의 Code]

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

/**
 * created by victory_woo on 2020/04/19
 * 연구소3.
 * 삼성 기출.
 */
public class Problem17142 {
    private static int min = Integer.MAX_VALUE;
    private static int n, m;
    private static int[][] map;
    private static ArrayList<Virus> list;
    private static int[] comArr;
    private static int[][] distance;
    private static boolean[][] visit;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        n = toInt(in[0]);
        m = toInt(in[1]);

        map = new int[n][n];
        distance = new int[n][n];
        list = new ArrayList<>();
        int index = 0, r;
        for (int i = 0; i < n; i++) {
            in = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = toInt(in[j]);
                //if (map[i][j] == 1) map[i][j] = -1;
                if (map[i][j] == 2) list.add(new Virus(index++, i, j));
            }
        }

        r = list.size();
        comArr = new int[m];
        combination(r, m, 0, 0);

        System.out.println(min == Integer.MAX_VALUE? -1 : min);
    }

    private static void combination(int k, int r, int index, int target) {
        if (r == 0) {
            print();
            return;
        }

        if (target == k) return;

        comArr[index] = target;
        combination(k, r - 1, index + 1, target + 1);
        combination(k, r, index, target + 1);
    }

    // 여기서 visit, distance 배열 초기화.
    private static void print() {
        int[][] copy = new int[n][n];
        visit = new boolean[n][n];
        LinkedList<Virus> q = new LinkedList<>();


        for (int index : comArr) {
            Virus virus = list.get(index);
            q.add(new Virus(virus.index, virus.x, virus.y));
            visit[virus.x][virus.y] = true;
            //distance[virus.x][virus.y] =-2;
            //copy[virus.x][virus.y] = -2;
        }

        while (!q.isEmpty()) {
            Virus cur = q.remove();

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if (visit[nx][ny]) continue;

                if (map[nx][ny] == 0) {
                    q.add(new Virus(-1, nx, ny));
                    //copy[nx][ny] = map[cur.x][cur.y] + 1;
                    distance[nx][ny] = distance[cur.x][cur.y] + 1;
                    visit[nx][ny] = true;
                }

            }

        }


        for (int i = 0; i < list.size(); i++) {
            Virus virus = list.get(i);
            if (!visit[virus.x][virus.y]) {
                distance[virus.x][virus.y] = -3;
            }
        }

        for (int index : comArr) {
            Virus virus = list.get(index);
            distance[virus.x][virus.y] = -2;
        }

/*        for (int a : comArr) System.out.print(a + " : " + list.get(a) + " ");
        System.out.println();*/

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (result < distance[i][j]) result = distance[i][j];
                //System.out.print(distance[i][j] + " ");
            }
            //System.out.println();
        }

        if (result < min) min =result;
    }

    private static int toInt(String value) {
        return Integer.parseInt(value);
    }

    static class Virus {
        int index;
        int x;
        int y;

        Virus(int index, int x, int y) {
            this.index = index;
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Virus{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}

바이러스를 퍼트리는 과정에서 감이 잘 잡히지 않아서 다른 풀이를 참고했다.

참고한 풀이는 규글님의 블로그이다.

풀이 순서는 다음과 같다.

  1. 입력을 받으면서 바이러스가 나오면 리스트를 통해 바이러스의 정보를 저장한다.
  2. 총 바이러스의 갯수에서 m개 만큼의 바이러스를 선택한다.(조합 사용)
  3. m개의 바이러스를 선택했으면, bfs 탐색을 이용해서 바이러스를 퍼트린다.
  4. 선택된 m개의 바이러스를 큐에 넣는다.
  5. bfs
    • copy 배열을 만든다.
    • 조합에서 선택되지 않은 바이러스는 비활성 바이러스로 -9로 표시한다.
    • 벽인 부분은 -1로 표시한다.
    • 조합을 통해 선택된 바이러스는 활성 바이러스로 -2로 표시한다.
    • 큐에서 바이러스를 하나씩 빼면서, 네 방향을 탐색하며 퍼트릴 수 있는 만큼 퍼트리며, copy 배열을 채운다.
    • 범위를 벗어나거나 방문한 적이 있거나 벽이거나 활성 바이러스의 경우는 건너뛴다.
    • 위의 조건에서 걸리지 않은 경우에는 빈칸이거나 비활성 바이러스인 경우이다. 이때는 큐에 넣어주고, 빈칸인 경우에는 이전까지 온 거리 + 1을 copy 배열의 위치에 넣어준다.
    • 비활성 바이러스인 경우에는 copy 배열을 갱신하지 않고 -9인 채로 유지한다.
    • copy 값이 0이 아닌 경우에는 이미 그 공간을 방문한 적이 있는 것이므로 최소값으로 갱신한다. copy 값보다 이전까지 온 거리가 더 작다면 그 작은 값으로 갱신한다.
  6. bfs 탐색이 끝나고 바이러스를 퍼트리지 못한 지점이 하나라도 존재하면 그 바이러스 조합은 종료한다.
  7. copy 배열을 탐색하며 가장 큰 값을 찾는다. 이 값은 바이러스를 퍼트리는데 걸린 총 시간을 의미한다.
  8. 그리고 copy 배열에서 0보다 큰 값이 하나라도 존재한다면 이는 바이러스를 퍼트린 시간을 계산할 수 있음을 의미한다. 따라서 result 값과 비교하여 가장 작은 값을 result 값에 갱신하도록 한다.
  9. copy 배열에서 0보다 큰 값이 하나라도 존재하는 것은 바이러스를 퍼트린 시간이 존재함을 뜻한다. 0보다 큰 값이 없다는 것은 이미 바이러스가 벽이 아닌 공간에 모두 퍼져 있어 더 이상 퍼트릴 공간이 없다는 것을 뜻하며 시간은 0이 된다.
  10. 0보다 큰 값이 하나라도 존재하면 퍼트린 시간이 존재하므로 이때는 더 작은 값을 max에 저장한다.

주의할 점은 활성 바이러스가 비활성 바이러스 칸에 가면 비활성 -> 활성이 된다는 것이다.

벽 : -1

비활성 바이러스 : -9

활성 바이러스 : -2

이렇게 설정하고 문제를 접근한다.

[Code]

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

/**
 * created by victory_woo on 2020/04/20
 * 연구소 3.
 * 삼성 기출.
 * <p>
 * 초기
 * 0 : 빈칸
 * 1 : 벽
 * 2 : 바이러스 위치.
 */
public class Problem17142_3 {
    private static int n;
    private static int result;
    private static int[][] map;
    private static int[] set;
    private static ArrayList<Virus> list;
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    // 상하좌우.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        n = toInt(in[0]);
        int m = toInt(in[1]);

        // 초기화.
        init();
        // 입력을 받으면서 바이러스의 위치를 리스트에 저장한다.
        for (int i = 0; i < n; i++) {
            in = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = toInt(in[j]);
                if (map[i][j] == 2) list.add(new Virus(i, j, 0));
            }
        }

        set = new int[m];

        // 총 바이러스의 개수에서 m개를 뽑는 조합을 진행한다.
        combination(list.size(), m, 0, 0);
        System.out.println(result == Integer.MAX_VALUE ? -1 : result);
    }

    private static void init() {
        map = new int[n][n];
        list = new ArrayList<>();
        result = Integer.MAX_VALUE;
    }

    private static void combination(int N, int R, int index, int target) {
        // 조합을 만든 경우, 그 조합을 기반으로 bfs 를 진행한다.
        if (R == 0) {
            bfs();
            return;
        }

        if (target == N) return;

        set[index] = target;
        combination(N, R - 1, index + 1, target + 1);
        combination(N, R, index, target + 1);
    }

    /*
     * bfs() 탐색을 진행해 바이러스를 퍼트린다.
     * 벽은 -1로 초기화.
     * 비활성 바이러스는 -9로 초기화.
     * 바이러스는 -2로 초기화.
     * */
    private static void bfs() {
        int[][] copy = new int[n][n];
        LinkedList<Virus> q = new LinkedList<>();
        boolean[][] visit = new boolean[n][n];

        // 활성 바이러스와 비활성 바이러스를 나눠서 처리한다.
        // 비활성 바이러스는  -9로 초기화한다.
        // 활성 바이러스는 -2로 초기화 하면서 큐에 넣고 방문 여부를 체크한다.
        for (int i = 0; i < list.size(); i++) {
            boolean flag = false;
            for (int index : set) {
                // 활성 바이러스인 경우.
                if (i == index) flag = true;
            }

            Virus virus = list.get(i);

            if (!flag) {
                copy[virus.x][virus.y] = -9;
            } else {
                copy[virus.x][virus.y] = -2;
                q.add(virus);
                visit[virus.x][virus.y] = true;
            }
        }

        // 벽 초기화.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1) copy[i][j] = -1;
            }
        }

        // bfs 탐색을 진행한다.
        while (!q.isEmpty()) {
            Virus cur = q.remove();
            int time = cur.time;

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                // 범위를 벗어나거나 방문한 적이 있거나 해당 정점이 벽이거나 혹은 활성 바이러스인 경우에는 건너뛴다.
                if (!isRange(nx, ny) || visit[nx][ny] || copy[nx][ny] == -1 || copy[nx][ny] == -2) continue;

                // 빈칸이거나 비활성 바이러스인 경우, 방문 여부를 체크하고 큐에 넣는다.
                // 이유는 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 -> 활성 상태로 바뀌기 때문이다.
                if (copy[nx][ny] == 0 || copy[nx][ny] == -9) {
                    visit[nx][ny] = true;
                    q.add(new Virus(nx, ny, time + 1));

                    // 빈칸인 경우, 처음 방문한 곳이기 때문에 해당 정점에 지금가지 걸린 시간 + 1을 넣어준다.
                    if (copy[nx][ny] == 0) {
                        copy[nx][ny] = time + 1;
                    } else {
                        // 이미 값이 있는 경우는 다른 바이러스에 의해서 이미 퍼지고 시간이 적혀 있는 것을 의미한다.
                        // 따라서 최소 시간으로 갱신이 가능하면 갱신한다.
                        // 왜냐하면 바이러스는 동시에 인접한 네 칸으로 퍼지기 때문이다.
                        // 현재 정점에 적힌 시간보다 지금까지 걸린 시간 + 1이 작으면 지금까지 걸린 시간 + 1로 갱신한다.
                        if (copy[nx][ny] > time + 1) copy[nx][ny] = time + 1;
                    }
                }
            }
        }

        int max = Integer.MIN_VALUE;

        if (isFinish(copy)) return;

        // 0보다 큰 값에 대해서 확인을 하며 가장 큰 값을 찾아 max 에 저장한다
        // 이는 바이러스를 모두 퍼트리는 데 걸린 시간을 구한다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (copy[i][j] < 0) continue;
                if (max < copy[i][j]) max = copy[i][j];
            }
        }

        // true : 바이러스를 퍼트리는 데 걸린 시간 중 최소 값을 구한다.
        if (isCompleted(copy)) {
            if (max < result) result = max;
        } else {
            result = 0;
        }
    }

    // 이미 벽과 충분한 바이러스로 꽉 차고 애초에 빈칸이 없는 경우에는 false 값을 반환한다.
    // 따라서 바이러스가 퍼지는 데 걸리는 시간은 없다. 0이다.
    // 0보다 큰 값이 하나라도 존재한다면 바이러스가 퍼진 시간을 계산할 수 있기 때문에 true 반환.
    private static boolean isCompleted(int[][] copy) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (copy[i][j] > 0) return true;
            }
        }
        return false;
    }

    // 바이러스가 모든 곳에 퍼졌는지 확인한다.
    // 모든 곳에 퍼졌다면 false 반환.
    // 퍼지지 않은 곳이 한 곳이라도 존재하면 true 반환.
    private static boolean isFinish(int[][] copy) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (copy[i][j] == 0) return true;
            }
        }
        return false;
    }

    // 범위 안에 들어오는 지 확인한다.
    private static boolean isRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < n;
    }

    private static int toInt(String value) {
        return Integer.parseInt(value);
    }

    static class Virus {
        int x;
        int y;
        int time;

        Virus(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
}