[백준 17141] 연구소 2 (자바)

백준 17141번 연구소 2 (자바)

 

 

 

출처

www.acmicpc.net/problem/17141

17141번: 연구소 2

 

 

 

문제

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

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

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

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

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

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

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

 

 

 

입력

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

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

 

 

 

출력

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

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

연구소 문제에서 더 조건이 추가된 문제다.

기존 연구소는 바이러스 확산 후 0의 개수만 세면 됐었는데 이 문제는 내가 임의로 바이러스 위치를 지정해 확산시킨 후 시간을 계산해야 한다.

 

1. 바이러스를 놓을 수 있는 위치를 담는 list를 만든다.

 

2. 바이러스 m개를 선택하면 확산시킨다.

 

3. temp 배열을 만들어 계산하고, time 배열을 만들어 시간을 계산한다.

 

4. 바이러스 list에서 확산시킬 바이러스 좌표를 temp, time 배열에 넣어주고 bfs로 확산을 시작한다.

(time배열이 0인 경우 확산하지 않기 위해 1을 넣었다. 마지막 연산 후 1을 빼줄 것이다.)

 

5. 변수(val) 하나를 만들어 시간 최대값을 계속 담는다.

 

 6. 확산 후 배열에 temp와 time이 0인 경우 모두 확산이 되지 않았기 때문에 max값으로 반환시킨다.

 

7. 결과값이 max이면 모든 빈칸에 퍼뜨리지 못한 것이기 때문에 -1을 반환하고, 아닌 경우 최댓값을 반환한다.

 

 

 

내 코드

package brute_force;

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

public class Laboratory2 {
	/**
	 * 백준 17141 연구소2 (https://www.acmicpc.net/problem/17141)
	 */
	private static int n, m;
	private static int[][] map;
	private static boolean[] visit;
	
	private static int[] dx = {-1, 0, 1, 0};
	private static int[] dy = {0, 1, 0, -1};
	
	private static int result = Integer.MAX_VALUE;
	private static int val;
	
	private static ArrayList<Virus> virusList = new ArrayList();
	
	public static void main(String[] args) throws IOException {

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(reader.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new int[n+1][n+1];
		
		for (int i=1; i<=n; i++) {
			st = new StringTokenizer(reader.readLine());
			for (int j=1; j<=n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 2) {
					virusList.add(new Virus(i, j));
					map[i][j] = 0;
				}
			}
		}
		
		visit = new boolean[virusList.size()];
		
		dfs(0,0);
		
		if (result == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(result-1);
		}
		
	}//main
	
	private static void dfs(int start, int count) {
		
		if (count >= m) {
			
			//바이러스 퍼뜨리기
			spreadVirus();
			
			//최소시간 비교
			result = Math.min(result, val);
			
		} else {
			
			for (int i=start; i<virusList.size(); i++) {
				if (!visit[i]) {
					visit[i] = true;
					dfs(start+1, count+1);
					visit[i] = false;
				}
			}
			
		}
		
	}


	private static void spreadVirus() {

		Queue<Virus> q = new LinkedList();
		
		int[][] temp = new int[n+1][n+1];
		int[][] time = new int[n+1][n+1];
		
		for (int i=1; i<=n; i++) {
			temp[i] = map[i].clone();
		}
		
		//방문처리 한 바이러스에 진짜 바이러스
		for (int i=0; i<virusList.size(); i++) {
			if (visit[i]) {
				map[virusList.get(i).x][virusList.get(i).y] = 0;
				time[virusList.get(i).x][virusList.get(i).y] = 1;
				q.add(virusList.get(i));
			}
		}
		
		val = 0;
		
		while (!q.isEmpty()) {
			
			Virus virus = q.remove();
			int qx = virus.x;
			int qy = virus.y;
			int qt = time[qx][qy];
			
			val = Math.max(val, qt);
			
			for (int i=0; i<dx.length; i++) {
				int nx = qx + dx[i];
				int ny = qy + dy[i];
				
				if (nx < 1 || ny < 1 || nx > n || ny > n || temp[nx][ny] != 0 || time[nx][ny] != 0) {
					continue;
				}
				
				//temp가 0이상이고, time이 0일 때
				if (temp[nx][ny] == 0 && time[nx][ny] == 0) {
					time[nx][ny] = qt + 1;
					temp[nx][ny] = 2;
					q.add(new Virus(nx, ny));
				}
			}
			
		}//while
		
		for (int i=1; i<=n; i++) {
			for (int j=1; j<=n; j++) {
				if (temp[i][j] == 0	&& time[i][j] == 0) {
					val = Integer.MAX_VALUE;
					return;
				}
			}
		}
		
		
	}

	static class Virus {
		int x, y;
		public Virus(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

 

 

 

고려할 점

1. 완전 탐색을 사용할 것

2. 시간계산할 배열을 만들 것

3. 모든 곳에 확산이 불가능한 경우를 생각할 것