[Java] 백준 17141번 : 연구소 2

1. 문제

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

17141번: 연구소 2

 

 

 

2. 풀이과정

1. 조합으로 바이러스를 놓을 장소를 선택한다.

2. M개를 선택하면, simulation인 dfs를 실행하여 걸린 시간을 count한다.

3. 바이러스를 퍼트린 공간 < (전체)-(벽의 수) 이면, 바이러스를 모두 못 퍼트린 상태로 처리한다.

import java.io.*;
import java.util.*;

public class Main {
    private static int N, M, map[][], blank, result;
    public static final int INF = 9999, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};;
    private static ArrayList<int[]> space;

    public static void combination(int cnt, int now, int selected[]){
        if(cnt==M){
            result = Math.min(result, bfs(selected));
            return;
        }
        if(now>=space.size()){
            return;
        }
        combination(cnt, now+1, selected);
        selected[cnt] = now;
        combination(cnt+1, now+1, selected);
    }

    public static int bfs(int selected[]){
        int sec = 0;
        Queue<int[]> q = new LinkedList<>();
        boolean visited[][] = new boolean[N][N];
        for(int idx : selected){
            int[] virus = space.get(idx);
            visited[virus[0]][virus[1]] = true;
            q.add(virus);
        }

        int cnt = M;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s=0; s<size; s++){
                int[] pos = q.poll();
                for(int i=0; i<4; i++){
                    int nx = pos[0] + dx[i];
                    int ny = pos[1] + dy[i];
                    if(nx<0 || nx>=N || ny<0 || ny>=N || map[nx][ny]==1){ continue;}
                    if(visited[nx][ny]){ continue;}
                    visited[nx][ny] = true;
                    cnt++;
                    q.add(new int[]{nx, ny});
                }
            }
            sec++;
        }
        if(cnt<blank){
            return INF;
        }
        return sec-1;
    }

    public static void main(String[] args) throws Exception{
        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];
        space = new ArrayList<>();
        result = INF;

        int wall = 0;
        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){
                    space.add(new int[]{i, j});
                }
                else if(map[i][j]==1){
                    wall++;
                }
            }
        }
        blank = N*N-wall;
        combination(0, 0, new int[M]);

        System.out.println((result==INF) ? -1 : result);
    }
}

 

 

결과