17142 연구소 3 Java
문제 🌐
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 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 와 비슷한 듯 안 비슷한 듯…. 가장 다른 점은 바이러스가 활성화 바이러스/비활성화 바이러스로 나눠진다는 것이다.
비활성화 바이러스 & 0인 부분 체크하기
그럼 활성화 바이러스는 무엇이 다른가? 하면… 바이러스가 비활성화 바이러스 위치에 가면 그 바이러스 또한 확산될 수 있다는 것이다. 따로 처리해 줘야 하나 싶었지만, 그냥 방문 처리를 하지 않고 q에 넣어 주면 되었다.
while (!q.isEmpty() && zero > 0) {
Node curr = q.poll();
int r = curr.r;
int c = curr.c;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (isValid(nr, nc) && !visited[nr][nc]) {
// 0일 때만 zeroCnt 감소
if (map[nr][nc] == 0)
zero--;
// 0일 때, 2일 때 모두 방문 체크 해 주고 q에 담기
visited[nr][nc] = true;
q.add(new Node(nr, nc));
vCnt[nr][nc] = vCnt[r][c] + 1;
}
}
}
시간 & 메모리 초과 이슈
바이러스가 다 퍼졌는지 확인할 때 다시 한번 방문 배열을 봤는데, 이렇게 돌려 보니까 시간 초과가 났다. 처음에 0인 칸의 개수를 세고 0이 되었는지, 아니면 0보다 큰 값으로 남아 있는지 확인해서 바이러스가 모두 퍼졌는지, 아니면 실패했는지 확인했다.
카운트 배열을 만들어 벽을 방문 체크 하고, 가장 큰 카운트 값을 갱신해 주는 건 앞선 연구소, 연구소 2 문제와 같다.
지금 보니까 벽(1)인 부분을 따로 체크해 줬는데, bfs 탐색을 할 때 조건을 map[nr][nc]!=1로 걸고 카운트 배열에서 최대값을 갱신했어도 됐을 것 같다.
방금 시도해 보니 메모리 상으로나 시간 상으로나 크게 다르지 않다….
문제를 처음 봤을 때는 감조차 안 왔는데, 이번에는 어떻게 접근하는 것이 좋을지 생각이 났고, 혼자 힘으로 다시 풀었다는 점이 뿌듯한 문제였다. 성장했음을 느껴…☆★
Full Solution
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N;
static int M;
static int vNum;
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
static ArrayList<Node> virus;
static int answer;
static int[][] map;
static class Node {
int r;
int c;
public Node(int r, int c) {
super();
this.r = r;
this.c = c;
}
@Override
public String toString() {
return "Node [r=" + r + ", c=" + c + "]";
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int zero = 0;
N = sc.nextInt();
M = sc.nextInt();
virus = new ArrayList<>();
answer = N * N;
map = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int temp = sc.nextInt();
map[i][j] = temp;
if (temp == 2) {
virus.add(new Node(i, j));
}
if (temp == 0)
zero++;
}
}
if (zero == 0)
System.out.println(0);
else {
vNum = virus.size();
Node[] comb = new Node[M];
boolean[] chk = new boolean[vNum];
combination(chk, 0, comb, 0, zero);
if (answer == N * N)
System.out.println(-1);
else
System.out.println(answer);
}
}
static void combination(boolean[] chk, int idx, Node[] result, int start, int zero) {
if (idx == M) {
Node[] temp = Arrays.copyOf(result, M);
bfs(temp, zero);
return;
}
for (int i = start; i < vNum; i++) {
if (!chk[i]) {
chk[i] = true;
result[idx] = virus.get(i);
combination(chk, idx + 1, result, i + 1, zero);
chk[i] = false;
}
}
}
static void bfs(Node[] temp, int zero) {
boolean[][] visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1)
visited[i][j] = true;
}
}
Queue<Node> q = new LinkedList<>();
int[][] vCnt = new int[N][N];
for (Node n : temp) {
q.add(n);
visited[n.r][n.c] = true;
vCnt[n.r][n.c] = 0;
}
while (!q.isEmpty() && zero > 0) {
Node curr = q.poll();
int r = curr.r;
int c = curr.c;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (isValid(nr, nc) && !visited[nr][nc]) {
if (map[nr][nc] == 0)
zero--;
visited[nr][nc] = true;
q.add(new Node(nr, nc));
vCnt[nr][nc] = vCnt[r][c] + 1;
}
}
}
boolean isOkay = true;
int max = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int now = map[i][j];
if (now == 1 || now == 2)
visited[i][j] = true;
if (!visited[i][j])
isOkay = false;
max = Math.max(max, vCnt[i][j]);
}
}
if (isOkay)
answer = Math.min(max, answer);
}
static boolean isValid(int r, int c) {
if (r < 0 || r >= N || c < 0 || c >= N)
return false;
return true;
}
}
Full Solution 2
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N;
static int M;
static int vNum;
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
static ArrayList<Node> virus;
static int answer;
static int[][] map;
static class Node {
int r;
int c;
public Node(int r, int c) {
super();
this.r = r;
this.c = c;
}
@Override
public String toString() {
return "Node [r=" + r + ", c=" + c + "]";
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int zero = 0;
N = sc.nextInt();
M = sc.nextInt();
virus = new ArrayList<>();
answer = N * N;
map = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int temp = sc.nextInt();
map[i][j] = temp;
if (temp == 2) {
virus.add(new Node(i, j));
}
if (temp == 0)
zero++;
}
}
if (zero == 0)
System.out.println(0);
else {
vNum = virus.size();
Node[] comb = new Node[M];
boolean[] chk = new boolean[vNum];
combination(chk, 0, comb, 0, zero);
if (answer == N * N)
System.out.println(-1);
else
System.out.println(answer);
}
}
static void combination(boolean[] chk, int idx, Node[] result, int start, int zero) {
if (idx == M) {
Node[] temp = Arrays.copyOf(result, M);
bfs(temp, zero);
return;
}
for (int i = start; i < vNum; i++) {
if (!chk[i]) {
chk[i] = true;
result[idx] = virus.get(i);
combination(chk, idx + 1, result, i + 1, zero);
chk[i] = false;
}
}
}
static void bfs(Node[] temp, int zero) {
boolean[][] visited = new boolean[N][N];
Queue<Node> q = new LinkedList<>();
int[][] vCnt = new int[N][N];
for (Node n : temp) {
q.add(n);
visited[n.r][n.c] = true;
vCnt[n.r][n.c] = 0;
}
while (!q.isEmpty() && zero > 0) {
Node curr = q.poll();
int r = curr.r;
int c = curr.c;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (isValid(nr, nc) && !visited[nr][nc] && map[nr][nc] != 1) {
if (map[nr][nc] == 0)
zero--;
visited[nr][nc] = true;
q.add(new Node(nr, nc));
vCnt[nr][nc] = vCnt[r][c] + 1;
}
}
}
boolean isOkay = true;
int max = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int now = map[i][j];
if (now == 1 || now == 2)
visited[i][j] = true;
if (!visited[i][j])
isOkay = false;
max = Math.max(max, vCnt[i][j]);
}
}
if (isOkay)
answer = Math.min(max, answer);
}
static boolean isValid(int r, int c) {
if (r < 0 || r >= N || c < 0 || c >= N)
return false;
return true;
}
}