17142 연구소 3 Java

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;
	}

}