[JAVA] BOJ(백준) - 연구소 3 - 17142

문제내용

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

17142번: 연구소 3

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

 

---

문제풀이

먼저 이문젠 로직은 옳바르게 생각했으나 구현을 제대로 하지 못했고, 구현한건 다른분꺼를 참고했다.

여튼 바이러스가 놓일수 있는곳 중에서 M개만큼 바이러스를 놓고 확산시켜보고 전부확산되기 까지 걸리는 시간을 구하는 문제다.

 

여기서 가장먼저 생각했던 로직은

1. 바이러스가 놓일수 있는곳 P개 중 M(M<=P)개를 놓을수 있다는 말을 봤을때 조합을 통해 모든 조합의 위치에 바이러스를 놔야겠다는 생각을 했고,(백트래킹)

2. 바이러스를 위치시키고 BFS로 확산시키면 되겠다는 생각을 했다.

3. 그리고 최종적으로 1~2번에서 확인한 조합마다 최종적으로 걸리는 시간을 계속해서 갱신해주면 되겠다고 생각했다.

 

결과적으로는 이 로직은 맞는 로직이였고, 이를 코드로 구현만 해내면된다.

다만 내가 구현하려 했던것과 조금 다른점은 2번 부분에선 처음에 입력받은 배열의 빈공간의 개수를 이용해 확산시킨다는 점이 달랐다.

나는 기존배열을 복사해 배열의 값을 바꾸는 식으로 생각을 했으나, 빈공간을 체크하는건 배열을 복사하고 계속 값을 바꿀 필요가 없기때문에 더 효율적인 로직이였다. 이부분은 코드를 보고 이해하자.

 

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static private int n,m,space,min;//배열크기, 바이러스개수, 빈공간, 최소시간
	static private int[][] init;//초기배열
	static private List<Virus> canVirus = new ArrayList<>();//바이러스가 놓일수 있는 위치들
	static private int[] dx = {-1,1,0,0};
	static private int[] dy = {0,0,-1,1};
	static private class Virus{
		int x;
		int y;
		int cnt;
		public Virus(int x, int y, int cnt) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		space=0;
		min = Integer.MAX_VALUE;
		init = new int[n][n];
		
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				init[i][j] = Integer.parseInt(st.nextToken());
				if(init[i][j]==2) canVirus.add(new Virus(i,j,0));
				else if(init[i][j]==0) space++;
			}
		}
		
		Virus[] th = new Virus[m];//조합을 통해 나온 바이러스의 위치들을 저장해둘 배열
		if(space==0) {//빈공간 0이면 다른거 돌릴 필요 없음.
			System.out.println(0);
			System.exit(0);
		}else back(0,0,th);
		
		//최소시간이 갱신됐다 -> 하나라도 바이러스 확산 ok, 최소시간이 그대로다 -> 바이러스 확산 모두 fail.
		if(min==Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(min);
	}
	
	public static void back(int depth, int idx, Virus[] th) {
		if(depth==m) {//바이러스 전부 놨을때.
			diffusion(th);//확산시키기
			return;
		}
		
		//조합
		for(int i=idx; i<canVirus.size(); i++) {
			th[depth] = canVirus.get(i);
			back(depth+1, i+1, th);
		}
	}
	
	public static void diffusion(Virus[] th) {
		Queue<Virus> q = new LinkedList<>();
		boolean[][] check = new boolean[n][n];
		
		//바이러스 놓은 위치들을 큐에 초기값으로 넣기.
		//방문처리.
		for(int i=0; i<th.length; i++) {
			Virus v = th[i];
			q.add(v);
			check[v.x][v.y]=true;
		}
		
		//빈공간 임시변수
		int subSpace=space;
		
		//확산시작
		while(!q.isEmpty()) {
			Virus cur = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				//배열의 크기를 넘어가는 경우, 방문했던 경우, 벽인 경우 제외.
				if(nx<0 || ny<0 || nx>=n || ny>=n || check[nx][ny] || init[nx][ny]==1) continue;
				
				//다음칸 빈공간일때 카운트 -1
				if(init[nx][ny]==0) subSpace--;
				
				//공간 없으면 최솟값 갱신.
				if(subSpace==0) {
					min = Math.min(min, cur.cnt+1);
					return;
				}
				
				//확산
				check[nx][ny] = true;
				q.add(new Virus(nx, ny, cur.cnt+1));
			}
		}
	}
}

---

마치며

다른부분은 크게 어려운 부분은 없다고 생각한다.

그리고 개인적으론 2번부분의 빈공간을 활용하는 로직은 다시한번 생각해보고 풀어 볼 필요가 있을듯 하다.