[BOJ 17142] 연구소3 (Java)

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

17142번: 연구소 3

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 Main_BOJ_17142 {
	static class Pos{
		int y, x;
		Pos(int y, int x){
			this.y=y;
			this.x=x;
		}
	}
	static int[] dy= {-1,1,0,0};
	static int[] dx= {0,0,-1,1};
	static int[][] map;
	static int N, M;
	static ArrayList<Pos> viruses=new ArrayList<>();
	static int answer=Integer.MAX_VALUE;
	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());
		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());
				if (map[i][j]==2) {
					viruses.add(new Pos(i,j));
				}
			}
		}
		if (check()) {
			comb(0,0, new int[M]);
			if (answer!=Integer.MAX_VALUE) {
				System.out.println(answer);
			}
			else {
				System.out.println(-1);
			}
		}
		else {
			System.out.println(0);
		}
	}
	
	private static boolean check() {
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j]==0) return true;
			}
		}
		return false; //빈칸 x 
	}



	private static void comb(int start, int cnt, int[] actives) {		//M개 고름  
		if (cnt==M) {
			int time=spread(actives);
			if (time!=-1) answer=Math.min(answer, time);
			return;
		}
		for (int i=start; i<viruses.size(); i++) {
			actives[cnt]=i;
			comb(i+1, cnt+1, actives);
		}
		
	}
	private static int spread(int[] actives) {	//다 안퍼지거나, answer 보다 크면 -1 
		Queue<Pos> q=new LinkedList<>();
		int[][] check=new int[N][N];
		boolean flag=false;
		int ans=0;
		for (int i=0; i<actives.length; i++) {
			int idx=actives[i];
			q.add(new Pos(viruses.get(idx).y, viruses.get(idx).x));
			check[viruses.get(idx).y][viruses.get(idx).x]=1;
		}
		while (!q.isEmpty()) {
			Pos p=q.poll();
			int time=check[p.y][p.x];
			if (map[p.y][p.x]==0 && time-1>answer) {
				flag=true;
				break;
			}
			if (map[p.y][p.x]==0) {
				ans=Math.max(ans, time-1);
			}
			for (int i=0; i<4; i++) {
				int ny=p.y+dy[i];
				int nx=p.x+dx[i];
				if (ny<0 || nx<0 || ny>=N || nx>=N) continue;
				if (map[ny][nx]!=1 && check[ny][nx]==0) {	//복제  
					check[ny][nx]=time+1;
					q.add(new Pos(ny,nx));
				}
			}
		}
		if (flag) return -1;
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j]==0 && check[i][j]==0) {
					return -1;
				}
			}
		}
		//isAllSpread
		
		return ans;
	}
}

이 문제의 포인트는 비활성화 바이러스일 경우, 바이러스가 퍼뜨린 시간으로 고려하지 않는다는 점이다.

 

가능한 바이러스의 개수 중 M개를 고른다.

M개 고른 것을 큐에 넣어주면서, BFS 탐색을 한다.

 BFS 탐색을 할 때마다, 큐에서 뽑는 위치가 0일 때, 그 시간이 answer보다 크면 탐색을 종료한다.

 위치 Pos를 큐에서 뽑을 때, map에서 그 위치가 빈칸이었을 경우, 그 위치까지 바이러스가 퍼진 시간을 저장해준다. 

 

빈칸이 아예 없을 경우를 생각하여 빈칸여부를 검사하는 check() 함수를 이용했다.

다른 분의 코드(https://yabmoons.tistory.com/254)를 보니,

바이러스가 다 퍼진 것은 따로 for 문을 돌아서 체크하지 않고 빈칸의 개수==방문한 빈칸의 개수가 일치하면 다 퍼졌다는 것으로 간주하였다.

그리고 total_time 이라는 변수를 이용해, 방문한 칸이 빈칸일 경우 그 시간을 변수에 저장해줘서,

최종적으로 answer 과 비교하는 것으로 했다. 어차피 BFS 탐색이므로 제일 마지막으로 방문한 빈칸에 바이러스가 퍼진 시간이 total_time에 저장되게 된다. 

빈칸이 아예 없을 경우에는 total_time이 0이므로, 스무스하게 출력 가능하다!