[17142] 연구소 3 - Java[자바]

 

 

| 문제 링크

 

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

17142번: 연구소 3

 

 

 

 

---

 

 

 

 

| 문제

 

1. NxN 크기의 연구소에 바이러스가 있습니다. N(4 ≤ N ≤ 50)
   0: 빈 칸
   1: 벽
   2: 바이러스
2. 바이러스는 0인 빈 칸으로 퍼져나갈 수 있으며, 1인 벽으로는 전파되지 못합니다.
3. 연구소에 놓인 바이러스 중 M개만 활성화 시킬 수 있으며, 나머지는 비활성화 상태로 활성화된 바이러스가 닿으면 활성화 상태로 바뀝니다. M(1 ≤ M ≤ 10)
4. M개의 바이러스를 활성화 시켰을 때, 연구소의 모든 빈 칸에 바이러스를 퍼트릴 수 있는 최소 시간(바이러스가 한 칸 이동하는데 걸리는 시간은 1로 계산) 을 출력하시오.
   만약, 모든 빈 칸에 바이러스를 퍼트릴 수 없다면, -1을 출력하시오.

 

 

 

 

---

 

 

 

 

| 풀이

 

1. 연구수 배열의 값을 입력 받으면서, '빈 칸의 값을 카운트', '바이러스들의 위치를 배열에 저장' 두 가지 행동을 같이 진행해줍니다.
   (빈칸이 0인 경우 0을 출력)
2. DFS를 통해 어떤 바이러스를 활성화 시킬 것인지 부분 수열을 구합니다.
3. 2번에서 구한 활성화된 바이러스 부터 BFS 탐색을 진행합니다.
4. 사방 탐색으로 바이러스를 퍼트리며, 퍼트린 공간을 방문처리 하여 재방문하지 않도록하며, 빈 칸의 카운트를 -1씩 감소시킵니다.
5. 카운트가 0이 되었을 때, 모두 전파하기 까지 걸린 시간의 최소값을 비교합니다.

 

 

 

 

---

 

 

 

 

| 풀이

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N;
	public static int M;
	public static int placeCnt=0;
	public static int min = Integer.MAX_VALUE;
	public static int[][] lab;
	public static List<int[]> virus = new ArrayList<>();
	public static int[][] virusFlag;
	public static boolean[][] visit;
	public static int[][] delta = {{-1,0},{0,1},{1,0},{0,-1}};
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		lab = new int[N][N];
		
		//연구소 값 입력
		for(int r = 0; r<N; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c = 0; c<N; c++) {
				int num = Integer.parseInt(st.nextToken());
				lab[r][c] = num;
				//바이러스는 별도 위치를 저장
				if(num == 2) {
					virus.add(new int[] {r,c,0});
				}
				//바이러스가 퍼질 수 있는 빈 칸의 개수를 카운트
				else if(num == 0)
					placeCnt++;
			}
		}
		
		//어떤 바이러스를 활성화 시킬지 여부를 표기하기 위한 배열
		virusFlag = new int[M][1];
		//만약 빈 칸이 없는 경우 0을 출력
		if(placeCnt==0)
			min = 0;
		//빈 칸이 있는 경우 dfs를 진행
		else
			dfs(0,0);
		//바이러스가 다 퍼질 수 없는 경우 -1을 출력
		if(min == Integer.MAX_VALUE)
			min = -1;
		bw.write(String.valueOf(min));
		br.close();
		bw.close();
	}
	
	public static void dfs(int depth, int idx) {
		//M개의 바이러스를 활성화 시킨 경우 bfs를 통해 바이러스를 확산 시킴
		if(depth==M) {
			visit = new boolean[N][N];
			bfs();
			return;
		}
		
		//몇 번째 바이러스를 활성화 시킬 것인지 부분 수열을 구함
		for(int i = idx; i<virus.size(); i++) {
			virusFlag[depth] = virus.get(i);
			dfs(depth+1, i+1);
		}
	}
	
	public static void bfs() {
		//빈 칸을 모두 바이러스로 채운 경우(cnt가 0이 되는 경우)를 확인하기 위해 빈 칸의 개수를 복사
		int cnt = placeCnt;
		Queue<int[]> que = new LinkedList<>();
		//활성화 시키 바이러스의 좌표값을 que에 입력
		for(int i = 0; i<M; i++) {
			que.add(virusFlag[i]);
			visit[virusFlag[i][0]][virusFlag[i][1]] = true;
		}
		
		while(!que.isEmpty()) {
			int[] rc = que.poll();
			int r = rc[0];
			int c = rc[1];
			int w = rc[2];
			
			//바이러스로부터 4방 탐색 진행
			for(int i = 0; i<4; i++) {
				int dr = r+delta[i][0];
				int dc = c+delta[i][1];
				//인덱스 범위를 벗어나거나, 이미 바이러스가 퍼졌거나, 벽인 경우는 continue
				if(dr<0 || dr>=N || dc<0 || dc>=N || visit[dr][dc] || lab[dr][dc]==1)
					continue;
				//바이러스를 퍼트렸으면 방문처리
				visit[dr][dc] = true;
				//바이러스를 퍼트린 공간이 빈 칸이라면 cnt--(바이러스를 퍼트린 공간이 비활성화된 바이러스 위치일수도 있기에)
				if(lab[dr][dc]==0)
					cnt--;
				//모든 칸에 바이러스를 퍼트렸다면, 바이러스가 퍼지기까지 걸린 시간의 min값을 구함
				if(cnt==0) {
					min = Math.min(min, w+1);
					return;
				}
				//아직 빈 칸이 남아있는 경우 바이러스를 게속 퍼트핌
				que.add(new int[] {dr,dc,w+1});
			}
		}
	}

}