1. 문제
설명
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.
연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.
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, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.
* 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초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.
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을 출력한다.
2. 풀이
지금까지 활용한 알고리즘들이 총출동하는 문제입니다.
그렇다고 쫄 필요는 없습니다.
늘 그랬듯이 계획을 세우고 차근차근 구현하면 됩니다.
계획1 - 바이러스의 좌표를 리스트에 담습니다.
List<int[]> viruses = new ArrayList<>(); // 바이러스를 담을 리스트
for (int i = 0; i < N; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
lab[i][j] = Integer.parseInt(stk.nextToken());
if (lab[i][j] == 2) {
viruses.add(new int[] {i, j});
}
}
} 활성화시킬 바이러스들의 좌표를 다 들고 있어야
M개의 바이러스에 대해서 승원이가 활성화를 시킬 수 있겠죠?
계획2 - DFS로 활성화할 바이러스를 고르는 모든 경우의 수를 만듭니다.
for (int i = startIndex; i < viruses.size(); i++) {
picked.add(viruses.get(i));
ans = Math.min(ans, min(depth + 1, i + 1, picked));
picked.pop();
}여기서 picked변수는 stack자료구조로서 우리가 뽑은 바이러스의 좌표들이 들어있습니다.
백준 - 치킨 배달 포스팅에서 설명했듯이 재귀 함수를 이런 식으로 설계하면
모든 조합을 구할 수 있습니다.
계획3 - BFS로 연구소에 바이러스를 퍼뜨립니다.
// 시뮬레이션을 진행할 연구소로 원본 연구소 복사
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
simulationLab[i][j] = lab[i][j];
}
}
// 뽑은 M개의 바이러스 좌표들을 q에 담고 활성화 표시(3)를 합니다.
for (int[] pick: picked) {
q.add(pick);
simulationLab[pick[0]][pick[1]] = 3;
}
while (!q.isEmpty()) {
int[] v = q.poll(); // 현재 바이러스의 정보
int y = v[0];
int x = v[1];
int t = v.length == 3
? v[2] - 1 // 시간 정보가 있을 때
: simulationLab[y][x] == 3
? -1 // 활성화된 바이러스일 때
: simulationLab[y][x] - 1; // 일반적으로 퍼뜨리는 경우일 때
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
// 범위를 벗어날 때
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
// 빈 칸도 아니고 비활성 바이러스도 아닐 때
if (simulationLab[ny][nx] != 0 && simulationLab[ny][nx] != 2) continue;
if (simulationLab[ny][nx] == 0) { // 빈 칸일 때
simulationLab[ny][nx] = t;
q.add(new int[] {ny, nx});
} else { // 바이러스일 때
simulationLab[ny][nx] = 3; // 활성화 표시
q.add(new int[] {ny, nx, t}); // 시간 정보도 같이 큐에 저장
}
}
}
int time = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 하나라도 빈 칸일 땐 무한값 리턴
if (simulationLab[i][j] == 0) return INF;
time = Math.min(time, simulationLab[i][j]);
}
}
return -time; 이 부분이 이 문제의 핵심입니다.
바이러스를 퍼뜨릴 때 시뮬레이션을 진행할 simulationLab에 시간 정보를 음수값으로 기록합니다.
그러면 visit배열을 선언하지 않아도 중복해서 탐색하지 않도록 프로그래밍이 가능합니다.
바이러스 활성화
[2, 0, 0] -> [3, -1, -2]이런 식으로요.
바이러스는 활성화됐다면 3으로 표시해 주고
바이러스가 이동할 때마다 -1, -2... 이런 식으로 시간을 음수로 남겨줬습니다.
근데 이러한 경우는 어떻게 처리할까요?
M은 1이고 맨 왼쪽의 바이러스를 활성화했다고 가정해보겠습니다.
바이러스 활성화
[2, 0, 0, 2, 0, 0] -> [3, -1, -2, 3, -4, -5]이런 식으로 오른쪽에 있는 바이러스를 활성화시키고 난 후
시간을 표시할 때 -1, -2... 가 아니라 -4, -5... 식으로 나아가야합니다.
이런 로직의 구현 코드가 이 부분이죠.
int t = v.length == 3
? v[2] - 1 // 시간 정보가 있을 때
: simulationLab[y][x] == 3
? -1 // 활성화된 바이러스일 때
: simulationLab[y][x] - 1; // 일반적으로 퍼뜨리는 경우일 때
// ... 탐색 코드...
// 활성화시킬 다른 바이러스일 때
simulationLab[ny][nx] = 3; // 활성화 표시
q.add(new int[] {ny, nx, t}); // 시간 정보도 같이 큐에 저장 simulationLab 변수에 바로 시간을 표시하는 게 아니라
큐에 시간 정보를 저장하고
다음 턴에 그 시간 정보가 있다면 그 시간 정보로
simulationLab 변수에 시간을 표시하는 식으로 나아가면 됩니다.
이런 식으로 구현을 해야하는 이유는 다음과 같습니다.
M은 1이고 맨 왼쪽의 바이러스를 활성화했다고 가정해보겠습니다.
바로 simulationLab에 시간을 표시한 경우
[2, 0, 0, 2] -> [3, -1, -2, -3]
정답은 -3, 즉 다시 양수로 뒤집어서 3이 돼버립니다.
하지만 위에서 구현한 로직대로
바이러스를 활성화 표시하고 그 다음부터 시간을 표시하도록 하면 어떨까요?
// 바이러스를 활성화 표시하고 다음부터 시간 표시
[2, 0, 0, 2] -> [3, -1, -2, 3]
정답은 -2, 즉 다시 양수로 뒤집어서 2가 나오니 저희가 원하는 답을 찾게됩니다.
3. 전체 코드
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N, M;
static final int INF = 987654321;
static int[][] lab;
static int[][] simulationLab;
static int[] my = {-1, 0, 1, 0};
static int[] mx = {0, 1, 0, -1};
static List<int[]> viruses = new ArrayList<>(); // 바이러스를 담을 리스트
static Queue<int[]> q = new LinkedList<>();
static int min(int depth, int startIndex, Stack<int[]> picked) {
// M개를 뽑았을 때
if (depth == M) {
// 계획3 - BFS로 연구소에 바이러스를 퍼뜨립니다.
// 시뮬레이션을 진행할 연구소로 원본 연구소 복사
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
simulationLab[i][j] = lab[i][j];
}
}
// 뽑은 M개의 바이러스 좌표들을 q에 담고 활성화 표시(3)를 합니다.
for (int[] pick: picked) {
q.add(pick);
simulationLab[pick[0]][pick[1]] = 3;
}
while (!q.isEmpty()) {
int[] v = q.poll(); // 현재 바이러스의 정보
int y = v[0];
int x = v[1];
int t = v.length == 3
? v[2] - 1 // 시간 정보가 있을 때
: simulationLab[y][x] == 3
? -1 // 활성화된 바이러스일 때
: simulationLab[y][x] - 1; // 일반적으로 퍼뜨리는 경우일 때
for (int dir = 0; dir < 4; dir++) {
int ny = y + my[dir];
int nx = x + mx[dir];
// 범위를 벗어날 때
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
// 빈 칸도 아니고 비활성 바이러스도 아닐 때
if (simulationLab[ny][nx] != 0 && simulationLab[ny][nx] != 2) continue;
if (simulationLab[ny][nx] == 0) { // 빈 칸일 때
simulationLab[ny][nx] = t;
q.add(new int[] {ny, nx});
} else { // 바이러스일 때
simulationLab[ny][nx] = 3; // 활성화 표시
q.add(new int[] {ny, nx, t}); // 시간 정보도 같이 큐에 저장
}
}
}
int time = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 하나라도 빈 칸일 땐 무한값 리턴
if (simulationLab[i][j] == 0) return INF;
time = Math.min(time, simulationLab[i][j]);
}
}
return -time;
}
int ans = INF;
// 계획2 - DFS로 활성화할 바이러스를 고르는 모든 경우의 수를 만듭니다.
for (int i = startIndex; i < viruses.size(); i++) {
picked.add(viruses.get(i));
ans = Math.min(ans, min(depth + 1, i + 1, picked));
picked.pop();
}
return ans;
}
public static void main(String[] args) throws Exception {
StringTokenizer stk = new StringTokenizer(br.readLine());
N = Integer.parseInt(stk.nextToken());
M = Integer.parseInt(stk.nextToken());
lab = new int[N][N];
simulationLab = new int[N][N];
// 계획 1 - 바이러스의 좌표를 리스트에 담습니다.
for (int i = 0; i < N; i++) {
stk = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
lab[i][j] = Integer.parseInt(stk.nextToken());
if (lab[i][j] == 2) {
viruses.add(new int[] {i, j});
}
}
}
int ans = min(0, 0, new Stack<>());
bw.write((ans == INF ? -1 : ans) + "");
bw.close();
}
}