[백준 17142 - Java] 연구소 3

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

 

문제

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

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

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

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

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

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

입력

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

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

출력

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

 

풀이

저는 활성 바이러스를 선택하는 모든 경우의 수에 대해 BFS 탐색을 수행하여 바이러스가 모두 퍼지는 경우를 찾는 방식으로 문제를 해결했습니다.

 

1. map을 입력받으면서 바이러스가 위치하는 좌표 따로 저장, 바이러스의 총 수, 빈칸의 총 수 count
2. 빈칸이 0개인 경우 그대로 0 출력 후 종료
3. 재귀를 호출하며 m개의 바이러스를 활성상태로 만든 후 bfs로 바이러스 퍼짐 확인하는 함수 호출
4. 바이러스 퍼짐 확인 함수에서는 bfs 수행하면서 남은 빈칸수 업데이트!
5. bfs수행중 빈칸 수가 0이되는 경우 종료 후 시간 비교

자세한 내용은 주석 참고해주세요!

import java.util.Scanner;
import java.util.*;

public class Main {
	static int n, m;
	static int[][] map = new int[50][50];
	static int room = 0;
	static int virusCnt = 0;
	static int[] virusR = new int[10];
	static int[] virusC = new int[10];
	static int answer = -1;
	static int[] R = {1, -1, 0, 0};
	static int[] C = {0, 0, 1, -1};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == 0)
					room++;
				if(map[i][j] == 2) {
					virusR[virusCnt] = i;
					virusC[virusCnt] = j;
					
					virusCnt++;
				}
			}
		}
		
		//원래 빈칸 없는 경우 바로 0 출력 
		if(room == 0) {
			System.out.println(0);
			return ;
		}
		dfs(0, 0);
		
		System.out.println(answer);
		
	}
	
	static void dfs(int idx, int cnt) {
		if(cnt == m) {
			check();
			return;
		}
		if(idx == virusCnt)
			return;
		
		//지금 바이러스 활성화 O
		int r = virusR[idx];
		int c = virusC[idx];
		map[r][c] = -1;
		dfs(idx+1, cnt+1);
		
		//활성화 X
		map[r][c] = 2;
		dfs(idx+1, cnt);
	}
	
	//BFS로 바이러스 퍼지는 시간 확인하는 함수
	static void check() {
		Queue<Virus> q = new LinkedList<>();
		int[][] temp = new int[50][50];
		int nonR = room;
		
		//활성된 바이러스들 큐에 추
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				temp[i][j] = map[i][j];
				if(map[i][j] == -1)
					q.add(new Virus(i, j, 0));
			}
		}
		
		int time = 0;
		
		while(!q.isEmpty()) {
			int nowR = q.peek().r;
			int nowC = q.peek().c;
			int nowT = q.peek().time;
			q.remove();
			
			for(int i=0; i<4; i++) {
				int nextR = nowR + R[i];
				int nextC = nowC + C[i];
				
				if(nextR<0 || nextR>=n || nextC<0 || nextC>=n)
					continue;
				//이미 바이러스 퍼트린 구역 or 
				if(temp[nextR][nextC] == 1 || temp[nextR][nextC] < 0)
					continue;
				
				// 비활성 바이러스 있던 곳이 아닌 빈칸!
				if(temp[nextR][nextC]==0)
					nonR--;
				
				//바이러스 퍼트린 위치는 -값 갖도록함
				temp[nextR][nextC] = -(nowT+1);
				q.add(new Virus(nextR, nextC, nowT+1));
				
			}
			//바이러스 다 퍼트린 경우 bfs종료!
			if(nonR == 0) {
				time = nowT+1;
				break;
			}
		}
		//바이러스 퍼트리기 성공 
		if(nonR == 0) {
			if(answer == -1)
				answer = time;
			else if(time < answer)
				answer = time;
		}
		//System.out.println();
	}
	
	static class Virus{
		int r;
		int c;
		int time;
		public Virus(int r, int c, int time) {
			this.r = r;
			this.c = c;
			this.time = time;
		}
		
	}
}