[백준] 17142 연구소3

문제보기

평범한 BFS 문제에 순열(조합)을 살짝 더해주면 된다.
다만 주의할 점은, 비활성화 된 세균 != 벽 이라는 점이다 ㅠㅠ
처음엔 뭣모르고 벽취급했다가 무한 틀렸습니다 늪에 빠졌었다(…)

1. 비활성화 된 세균은 통과할 수 있다.
2. 그러나 이것은 걸린 최종 시간에 포함되서는 안된다.
   즉 bfs를 통해 얻은 최대 시간 중 마지막 칸을 비활성화 된 세균을 밟은 경우는 무효라는 뜻이다. 코드를 보며 상세히 설명하도록 하겠다..

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

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

public class Main {
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	
	// 다음순열을 구하는 메서드
	static boolean next_perm(int[] arr) {
		int i = arr.length-1;
		while( i > 0 && arr[i-1] >= arr[i]) {
			i--;
		}
		if(i <= 0) {
			return false;
		}
		int j = arr.length-1;
		while(arr[j] <= arr[i-1]) {
			j--;
		}
		
		int temp = arr[j];
		arr[j] = arr[i-1];
		arr[i-1] = temp;
		
		int k = arr.length -1;
		while(i < k ) {
			temp = arr[k];
			arr[k] = arr[i];
			arr[i] = temp;
			i++;
			k--;
		}
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		List<Pair> virus = new ArrayList<Pair>();
		
		// 본격적으로 맵을 입력받는다 
		int[][] map = new int[n][n];
		for(int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < n ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				// 기본적으로 맵에는 걸린 시간이 기록될 것이므로 시간과 관계없는 속성들은 0 이하로 맞춰줘야 한다.
				// 통과 가능한 길 -> -1로 
				if(map[i][j] == 0) map[i][j] = -1;
				// 바이러스가 있는 곳 -> -2로
				// 또한 바이러스 리스트에 넣어준다
				if(map[i][j] == 2) {
					virus.add(new Pair(i, j));
					map[i][j] = -2;
				}
				// 벽이 있는 곳 -> 0으로
				if(map[i][j] == 1) {
					map[i][j] = 0;
				}
			}
		}
		// 최소시간 초기화 (넉넉하게 해줬는데 2500만 줘도 충분할것임)
		int min = 200000000;
		// 세균을 선택할 조합을 표현할 배열 
		int[] order = new int[virus.size()];
		int idx = virus.size()-1;
		for(int i = 0 ; i < m ; i++) {
			order[idx--] = 1;
		}
		
		myloop:
		do {
			// 이 반복문을 여러번 돌릴거라 매번 map을 복사해서 사용하겠다
			int[][] newMap = new int[n][n];
			for(int i = 0 ; i < n ; i++) {
				System.arraycopy(map[i], 0, newMap[i], 0, n);
			}
			
			//	bfs 시작
			Queue<Pair> q = new LinkedList<>();
			for(int i = 0 ; i < virus.size(); i++) {
				if(order[i] == 1) { // 선택된 세균은 
					q.add(virus.get(i)); // 활성화 되어 큐에 들어간다 
					// 시작 시간은 0
					newMap[virus.get(i).x][virus.get(i).y] = 0; 
				}
			}
			
			while(!q.isEmpty()) {
				Pair p = q.remove();
				int x = p.x;
				int y = p.y;
				
				for(int k = 0 ; k < 4 ; k++) {
					int nx = x + dx[k];
					int ny = y + dy[k];
					
					if(nx >= 0 && nx < n && ny >= 0 && ny < n) {
						// 빈 길이거나 비활성화 된 세균은 통과할 수 있다
						if(newMap[nx][ny] == -1 || newMap[nx][ny] == -2) {
							newMap[nx][ny] = newMap[x][y] + 1;
							q.add(new Pair(nx, ny));
						}
					}
				}
			}
			// 걸린 최종시간을 계산한다 
			int time = 0;
			for(int i = 0 ; i < n ; i++) {
				for(int j = 0 ; j < n ; j++) {
					// 아직 세균이 도달하지 못한곳이 있다면 이 시도는 실패한것이므로 다음 순열로 넘어가야 한다.
					if(newMap[i][j] == -1) {
						continue myloop;
					}
					// 원래 비활성화 된 세균이 있던 곳이라면 걸린 최종시간에 포함되어선 안되므로 0 으로 바꿔준다 
					if(map[i][j] == -2) {
						newMap[i][j] = 0;
					}
					// 맵에서 가장 큰 값을 찾아주면 걸린 최종시간이 된다
					if(newMap[i][j] > time) {
						time = newMap[i][j];
					}
				}
			}
			// 최소시간 갱신 
			if(time < min) {
				min = time;
			}
			
		}while(next_perm(order));
		
		// 출력 : min 값이 초기값과 같다면 어떤 시도를 해도 바이러스를 퍼뜨릴 수 없는것이다. 실패 : -1
		System.out.println(min == 200000000 ? -1 : min);
	}
}