1.문제

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

2.코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main{
	static int M,N;
	static int[][] map;
	static Stack<int[]> virus;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        virus = new Stack<int[]>();
        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());
        	}
        }
        
        //바이러스 고르자
        choice(0,0,0);
        
        bw.write(((result==Integer.MAX_VALUE)?-1:result-1)+"\n");
        bw.flush();
        bw.close();
        br.close();
    }
    static int result = Integer.MAX_VALUE;
	private static void choice(int y, int x, int n) {
    //M개만큼 고르면 값 비교		
		if(n==M) {
			result = Math.min(bfs(),result);
		}
		//x가 범위 벗어나면 다음줄로
		if(x==N) {
			x=0;
			y++;
		}
		//바이러스 둘곳을 찾는다.(DFS)
		while(y<N) {
      //둘수있는곳이면 스택에 넣고 다음 바이러스를 넣으러 간다.
			if(map[y][x]==2) {
				map[y][x] = 3;
				virus.add(new int[] {y,x});
				choice(y,x+1,n+1);
				virus.pop();
				map[y][x] = 2;
			}
			
			x++;
			if(x==N) {
				x=0;
				y++;
			}
		}
	
	}
	static int[] my = {1,-1,0,0};
	static int[] mx = {0,0,-1,1};
	private static int bfs() {
		int[][] temp = new int[N][N];
		//지도 복제 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				temp[i][j] = map[i][j];
			}
		}
		//BFS 할거임
		Queue<int[]> que = new LinkedList<int[]>();
		//처음 위치의 바이러스들 가져온다
		for(int i=0; i<M; i++) {
			que.add(virus.get(i));
		}
		
		int result = 0;
		
		while(!que.isEmpty()) {
			int size = que.size();
			
			while(size-->0) {
				int[] curr = que.poll();
				
				int y = curr[0];
				int x = curr[1];
				
				for(int i=0; i<4; i++) {
					int ny = y+my[i];
					int nx = x+mx[i];
					
					if(ny<0 || ny>=N || nx<0 || nx>=N || temp[ny][nx]==3 || temp[ny][nx]==1) continue;
					
					temp[ny][nx] = 1;
					que.add(new int[] {ny,nx});
				}
			}
			result++;
		}
		
		//바이러스 모두 퍼졌는지 확인 후에 결과를 반납한다.
		boolean check = true;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(temp[i][j]==0) {
					check = false;
					break;
				}
			}
			if(!check) break;
		}
		
		
		
		return (check)?result:Integer.MAX_VALUE;
	}
}

3.Reveiw

DFS사용 배치할 바이러스들을 스택에 넣어준다.
BFS로 바이러스가 몇초만에 퍼지는지 확인한다.
바이러스가 다 퍼졌는지 확인한다.

-끝-