알고리즘/PS - 백준

[백준 17142 - Java] 연구소 3

excited-hyun 2021. 9. 30. 15:41
반응형

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

 

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

 

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 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;
		}
		
	}
}

 

728x90
반응형