백준_17142_연구소3

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

17142번: 연구소 3

문제를 읽었다면 알겠지만 바이러스 n(문제에서 입력값으로 주어짐) 개중에 m 개를 활성화로 선택한다.

이때 조건을 보면 활성화 바이러스가 퍼지면서 비활성 바이러스에 닿으면 비활성 바이러스는 활성화 바이러스로 바뀐다. 사실 이 부분은 신경 쓰지 않아도 된다.

1. 비활성 바이러스가 활성 바이러스로 변해도 퍼지는데 1초가 걸린다.

2. 활성바이러스가 퍼진 곳에서 다 싶어지는 데까지 1 초가 걸린다.

위 1, 2 번은 똑같은 경우이다. 바이러스가 퍼지는 위치에 비활성화 바이러스가 있든 말든 신경 쓰지 않아도 된다.(하지만 지도에는 비활성 바이러스를 잘 표시해줘야 한다!) 

즉 바이러스들의 위치만 잘 표시해준다면 초기 활성화 바이러스 기준으로 문제를 풀어나가면 된다.

 

풀이 순서

1. 백트래킹을 이용하여 활성화시킬 바이러스를 선택한다.

2. 선택된 바이러스를 퍼뜨려 최소 시간 값을 구한다.

   2-1. bfs(바이러스를 퍼뜨리는)를 한번 돌 때마다 시간을 체크해야 한다.

 

다음은 전체 코드이다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Bj_17142 {
	static int n,m;
	static int[][] map;
	static boolean check[][];
	static boolean[] flag;
	static int xx[] = {0, 0, 1, 0, -1};
	static int yy[] = {0, 1, 0, -1, 0};
	static int answer = Integer.MAX_VALUE;
	static LinkedList<Vius> vius = new LinkedList<Vius>();
	static LinkedList<Vius> selectedVius = new LinkedList<Vius>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n + 1][n + 1];
		for(int i = 1; i <= n; i++) {		
			for(int j = 1; j <= n; j++){
				int value = sc.nextInt();
				if(value == 2) {
					vius.add(new Vius(i, j));
				}
				map[i][j] = value;
			}
		}
		
		flag = new boolean[vius.size()];		
		selectVius(0, m, 0, selectedVius);
		System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
		//백트래킹으로 바이러스 선택하장
	}
	
	public static void selectVius(int cnt, int m, int index, LinkedList<Vius> selectedVius) {
		if(cnt == m) {
			// 바이러스 선택했으니까 바이러스 퍼뜨리장 ㅎㅎ..
			spreadVius(selectedVius);
			return;
		}
		for(int i = index; i < flag.length; i++) {
			if(!flag[i]) {
				selectedVius.add(new Vius(vius.get(i).x, vius.get(i).y));
				flag[i] = true;
				selectVius(cnt + 1, m, i, selectedVius);
				flag[i] = false;
				selectedVius.removeLast();
			}
		}
	}
	
	public static void spreadVius(LinkedList<Vius> selectedVius) {
			int[][] copyMap = new int[n + 1][n + 1];
			//배열 복사
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= n; j++) {
					copyMap[i][j] = map[i][j];
				}
			}
			//바이러스 퍼뜨리기
			int count = 0;
			check = new boolean[n + 1][n + 1];
			Queue<Vius> q = new LinkedList<Vius>();
			for(int i = 0; i < selectedVius.size(); i++) {
				check[selectedVius.get(i).x][selectedVius.get(i).y] = true;
				q.add(new Vius(selectedVius.get(i).x, selectedVius.get(i).y));
			}
			
			while(true) {
				// 바이러스가 다퍼졌다면 종료;
				if(checkMap(copyMap)) {
					answer = Math.min(answer, count);
					return;
				}
				// 카운트가 최소값과 이미같다면 종료
				if(count == answer) {
					return;
				}
				// 바이러스를 퍼뜨리기
				Queue<Vius> tempQ = new LinkedList<Vius>();
				while(!q.isEmpty()) {
					
					Vius temp = q.poll();
					for(int i = 1; i <= 4; i++) {
						int new_x = temp.x + xx[i];
						int new_y = temp.y + yy[i];
						if(new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= n) {
							if(copyMap[new_x][new_y] != 1 && !check[new_x][new_y]) {
								check[new_x][new_y] = true;
								copyMap[new_x][new_y] = 2;
								tempQ.add(new Vius(new_x, new_y));
							}
						}
					}
				}
				count++;
				//더이상 퍼뜨릴게 없다면 종료
				if(tempQ.isEmpty()) {
					return;
				}else {
					// 다음에 퍼뜨릴거 q 에넣어주자 ! bfs 한번당 카운트 해줘야하기떄문
					while(!tempQ.isEmpty()) {
						q.add(tempQ.poll());
					}
				}
			
			}
	}
	public static boolean checkMap(int[][] copyMap) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(copyMap[i][j] == 0) {
					return false;
				}	
			}
		}
		return true;
	}
	
}

class Vius {
	int x,y;
	Vius(int x, int y){
		this.x= x;
		this.y= y;
	}
}