[Java] 백준 17142번 : 연구소 3*

문제

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

17142번: 연구소 3

 

 

풀이 과정

바이러스 중에서 M개를 선택하는 조합 + 각 바이러스를 빈칸 또는 비활성 바이러스로 퍼뜨리는 BFS탐색으로 풀이할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, blank, min;
    static int[][] map;
    static List<Node> virus;

    static class Node{
        int x, y;

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

    public static void main(String[] args) {
        try{
            init();
            if(blank == 0){
                min = 0;
            }
            else{
                selectVirus(0, 0, new Node[M]);
            }
        }catch (Exception e){
            e.printStackTrace();
        }

        System.out.println((min == Integer.MAX_VALUE) ? -1 : min);
    }

    public static void init() 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];
        virus = new ArrayList<>();
        min = Integer.MAX_VALUE;

        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] == 0){
                    blank++;
                }
                else if(map[i][j] == 2){
                    virus.add(new Node(i, j));
                }
            }
        }
    }

    public static void selectVirus(int cnt, int idx, Node[] selectedVirus){
        if(cnt >= M){
            getMinTime(selectedVirus);
            return;
        }

        for(int i=idx; i<virus.size(); i++){
            selectedVirus[cnt] = virus.get(i);
            selectVirus(cnt + 1, i + 1, selectedVirus);
        }
    }

    public static void getMinTime(Node[] viruses){
        //1이 아닌 모든 곳에 퍼트리기 가능
        //2만 남았으면 cnt할 필요 없음
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        Queue<Node> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];

        //1. virus 위치 넣기
        for(Node virus : viruses){
            visited[virus.x][virus.y] = true;
            q.add(virus);
        }

        //2. 퍼트리기
        int result = 0, infected = 0;
        while(!q.isEmpty()){
            int size = q.size();
            while(size-- > 0){
                Node now = q.poll();
                if(map[now.x][now.y] == 0){
                    infected++;
                }
                for(int i=0; i<4; i++){
                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];
                    if(nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny]) continue;
                    visited[nx][ny] = true;
                    if(map[nx][ny] != 1){
                        q.add(new Node(nx, ny));
                    }
                }
            }
            //다 감염시켰으면 종료
            if(infected == blank){
                min = Math.min(min, result);
                return;
            }
            result++;
        }
        
    }

}

 

여기서 조합을 구하고 BFS탐색을 하지 않고, BFS탐색을 한 후, 조합대로 계산하면 더 효율적으로 처리할 수 있다. 각 바이러스마다 한번의 BFS탐색만 거치도록 하는 것이다.

 

각 바이러스에서 빈 칸을 감염시키는 데 걸리는 시간을 각 칸에 미리 저장하고, 조합마다 M개의 바이러스 중 어느 바이러스가 해당 칸을 감염시키는 데 가장 적게 걸리는 지 구한다.

결과는 전체 빈 칸을 감염시키는 데 걸리는 최소 시간 중 가장 큰 값을 구하고, 여기서 가장 작은 값이 정답이 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, blank, result;
    static int[][] map;
    static int[][][] distance;
    static List<Node> viruses;

    static class Node{
        int x, y;

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

    public static void main(String[] args) {
        try{
            init();
            if(blank == 0){
                result = 0;
            }
            else{
                for(int i=viruses.size()-1; i>=0; i--){
                    updateDistance(i);
                }
                selectVirus(0, 0, new int[M]);
            }
        }catch (Exception e){
            e.printStackTrace();
        }

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

    public static void init() 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];
        viruses = new ArrayList<>();
        result = Integer.MAX_VALUE;

        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] == 0){
                    blank++;
                }
                else if(map[i][j] == 2){
                    viruses.add(new Node(i, j));
                }
            }
        }
        distance = new int[viruses.size()][N][N];
    }

    public static void updateDistance(int idx){
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        Queue<Node> q = new LinkedList<>();

        for(int i=0; i<N; i++){
            Arrays.fill(distance[idx][i], Integer.MAX_VALUE);
        }
        //1. virus 위치 넣기
        Node virus = viruses.get(idx);
        distance[idx][virus.x][virus.y] = 0;
        q.add(virus);

        //2. 퍼트리기
        while(!q.isEmpty()){
            Node now = q.poll();

            for(int i=0; i<4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx<0 || nx>=N || ny<0 || ny>=N || map[nx][ny]==1) continue;

                if(distance[idx][nx][ny] == Integer.MAX_VALUE){
                    distance[idx][nx][ny] = distance[idx][now.x][now.y] + 1;
                    q.add(new Node(nx, ny));
                }
            }
        }
    }

    public static void selectVirus(int cnt, int idx, int[] selectedVirus){
        if(cnt >= M){
            result = Math.min(result, getMinTime(selectedVirus));
            return;
        }

        for(int i=idx; i<viruses.size(); i++){
            selectedVirus[cnt] = i;
            selectVirus(cnt + 1, i + 1, selectedVirus);
        }
    }

    public static int getMinTime(int[] selectedVirus){
        int maxDistance = 0;

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(map[i][j] != 0) continue;

                int min =  distance[selectedVirus[0]][i][j];
                for(int k=1; k<M; k++){
                    min = Math.min(min, distance[selectedVirus[k]][i][j]);
                }
                maxDistance = Math.max(maxDistance, min);
            }
        }
        return maxDistance;
    }

}