17141 연구소 2 Java

문제 🌐

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×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 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 5

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

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
5 - 3 2 3 4 5

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

입력

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

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

출력

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

접근 방법

조합을 구한 후 bfs 탐색을 한다는 점에서 연구소 문제와 접근 방법은 같습니다. 이 문제의 경우 바이러스를 놓을 위치를 조합한다는 점에서 다릅니다.

1. 입력받을 때, 바이러스의 위치를 세고 ArrayList에 담는다.
2. combination 메소드에서 M개의 바이러스 조합을 구한다.
3. 바이러스를 꺼내고 bfs 탐색을 한다.
4. 바이러스가 다 퍼지면 걸리는 시간을 출력하고, 완전히 퍼지지 않았을 때는 -1을 출력한다.

입력 받고 조합 구하기

	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));
			}
		}
	}
	
	vNum = virus.size();
	Node[] comb = new Node[M];
	boolean[] chk = new boolean[vNum];
	
	combination(chk, 0, comb, 0);

	static void combination (boolean[] chk, int idx, Node[] result, int start) {
		if (idx == M) {
			Node[] temp = Arrays.copyOf(result, M);
			
			bfs(temp);
			
			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);
				chk[i] = false;
			}
		}
	}

바이러스 퍼뜨리기

여기서 방문 체크를 할 때, 입력받을 때에 벽을 먼저 체크해 두고 깊은 복사를 할지 말지 고민했다.

하지만 새 배열을 만들고 이후에 방문하지 않은 곳이 있는지 확인해야 하기 때문에 그 부분에서 함께 처리하기로 결정했다. 만약 벽이라면, 미리 방문 체크를 해 주고 카운트 배열의 값을 갱신했다.

	static void bfs (Node[] temp) {
		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()) {
			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])  {
					q.add(new Node(nr, nc));
					visited[nr][nc] = true;
					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++) {
				if (map[i][j] ==1) visited[i][j] = true;
				if (!visited[i][j]) isOkay = false;
				max = Math.max(max, vCnt[i][j]);
			}
		}
		
		if (isOkay) answer = Math.min(max, answer);
		
	}

답 찾기

if (answer == N*N) System.out.println(-1);
else System.out.println(answer);

answer 초기화할 때, 나올 수 없는 값으로 초기화하고 바이러스가 다 퍼졌을 때 answer를 최소값으로 매번 갱신했다. 만약 바이러스가 다 퍼졌을 경우에는 NN 보다 작아졌을 것이므로, NN으로 남아 있다면 -1을 출력하고, 그렇지 않다면 갱신된 answer를 출력했다.

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);
		
		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));
				}
			}
		}
		
		vNum = virus.size();
		Node[] comb = new Node[M];
		boolean[] chk = new boolean[vNum];
		
		combination(chk, 0, comb, 0);
		
		if (answer == N*N) System.out.println(-1);
		else System.out.println(answer);
		
	}
	
	static void combination (boolean[] chk, int idx, Node[] result, int start) {
		if (idx == M) {
			Node[] temp = Arrays.copyOf(result, M);
			
			bfs(temp);
			
			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);
				chk[i] = false;
			}
		}
	}
	
	static void bfs (Node[] temp) {
		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()) {
			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])  {
					q.add(new Node(nr, nc));
					visited[nr][nc] = true;
					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++) {
				if (map[i][j] ==1) 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;
	}
	
}