[백준] 11741번 연구소2 (java, flood fill)

www.acmicpc.net/problem/17141

17141번: 연구소 2

조합으로 바이러스 놓을 수 있는 위치 m개를 골라 놓은 뒤 동시에 퍼지게 한다. 

bfs안에서 매번 새로운 큐의 사이즈 만큼 먼저 돌려준다. (다음에 들어오는 바이러스 위치들은 다음에 처리해준다.)

채워진 곳 중에서 가장 높은 수가 실제 퍼지는 데 걸린 시간이다.

 

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

class Pos{
	int y,x;

	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class Main {
	static int n,m;
	static int[][] map;
	static int xpos[]= {1,-1,0,0};
	static int ypos[]= {0,0,1,-1};
	static boolean[][] check;
	static boolean vis[];
	static ArrayList<Pos> list=new ArrayList<>();
	static Queue<Pos> q;// bfs 큐
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new int[n][n];
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j]=sc.nextInt();
				if(map[i][j]==1)map[i][j]=-1;//벽은 진행에 방해안되게 -1로 만들어줌
				if(map[i][j]==2) { //바이러스는 위치만 저장해주고 0으로 바꿔준다.
					list.add(new Pos(i,j));
					map[i][j]=0;
				}
			}
		}

		vis=new boolean[list.size()];
		comb(0,0);
		System.out.println(answer==Integer.MAX_VALUE?-1:answer);
	}
	private static void comb(int cnt, int start) {
		if(cnt==m) {
			bfs();
			return;
		}
		for (int i = start; i < list.size(); i++) {
			if(vis[i])continue;
			vis[i]=true;
			comb(cnt+1,i+1);
			vis[i]=false;
		}
		
	}
	private static void bfs() {
		int[][] temp=copy();
		int cnt=0;
		//벽은 -으로 바꾸고 바이러스는 0, 시간은 1,2,3,4로 표시한다.
		int time=1;
		while(q.size()!=0) {
			int size=q.size();
			for (int i = 0; i < size; i++) {
				Pos cur=q.poll();
				int y=cur.y;
				int x=cur.x;
				if(temp[y][x]>cnt)cnt=temp[y][x];
				for (int k = 0; k < 4; k++) {
					int yy=y+ypos[k];
					int xx=x+xpos[k];
					if(yy<0 || xx<0 || yy>=n|| xx>=n)continue;
					if(check[yy][xx])continue;
					if(temp[yy][xx]==0) {
						check[yy][xx]=true;
						temp[yy][xx]=time;
						q.add(new Pos(yy,xx));
					}
				}
			}
			time++;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(temp[i][j]==0)return;
			}
		}
		if(answer>cnt)answer=cnt;
	}
	
	private static int[][] copy() {
		q=new LinkedList<Pos>();
		check=new boolean[n][n];
		int[][] c=new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				c[i][j]=map[i][j];
			}
		}
		for (int i = 0; i < list.size(); i++) {
			if(vis[i]) {
				int y=list.get(i).y;
				int x=list.get(i).x;
				c[y][x]=-2;//바이러스
				q.add(new Pos(y,x));
				check[y][x]=true;
			}
		}
		return c; //복사한 배열 놓음
	}
}