백준 17121 연구소2 [JAVA]

17141번: 연구소 2

 

풀이 방법

모든 빈칸에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제였습니다.

 

저는 먼저 이렇게 크게 

1. 바이러스가 놓일 수 있는 연구소 위치를 list에 담기

2. 조합을 이용해 전체 바이러스 개수 중 M개 선택하기

3. 선택한 바이러스 퍼뜨리기

4. 바이러스가 퍼지는 최소 시간 구하기

이 순서로 구현했습니다.

 

조합을 이용해 M개의 바이러스 놓을 칸을 정했다면 spread() 메서드에서 상 하 좌 우로 이동하면서

바이러스를 퍼지게했습니다. 모든 바이러스가 퍼진 뒤에는, 최소 시간을 구해야 하기 때문에 time() 메서드를 통해서

모든 빈 칸에 바이러스가 퍼졌는지 확인과 함께 퍼뜨리는 최소 시간을 구해주었습니다.

이렇게 모든 바이러스가 놓일 수 있는 경우를 확인한 후 가장 최소 시간을 마지막에 출력해주었습니다.

 

 

코드

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_BJ_17121_연구소2 {
    
    static class info{
        int x, y;
 
        public info(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }
        
    }
    
    static int N,M, time = Integer.MAX_VALUE;
    static int [][] map, copy;
    
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
 
    static ArrayList<info> list = new ArrayList<>();
    static ArrayList<info> select = new ArrayList<>();
    static Queue<info> queue = new LinkedList<>();
    static boolean [][] selected;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //연구소 크기
        M = Integer.parseInt(st.nextToken()); //바이러스 개수
        
        map = new int[N][N];
        selected = new boolean[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]==1) map[i][j]= -1;
                else if(map[i][j]==2) {
                    list.add(new info(i,j));
                    map[i][j] =0;
                }
            }
        }
        comb(0,0);
        if(time==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(time);
    }
    
    public static void comb(int cnt, int start) {
        if(cnt==M) {
            // 바이러스 퍼지기 & 최소 시간 확인
            spread();
            return;
        }
        
        for(int i=start;i<list.size();i++) {
            int x = list.get(i).x;
            int y = list.get(i).y;
            if(selected[x][y]) continue;
            
            select.add(new info(x,y));
            selected[x][y] = true;
            
            comb(cnt+1,i+1);
            selected[x][y] = false;
            select.remove(select.size()-1);
        }
        
    }
    
    public static void spread() {
        
        transfer();
        copy();
    
        while(!queue.isEmpty()) {
            info temp = queue.poll();
            
            for(int i=0;i<4;i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];
                
                if(range(nx,ny) && copy[nx][ny]==0 && !selected[nx][ny]) {
                    copy[nx][ny] = copy[temp.x][temp.y]+1;
                    queue.add(new info(nx,ny));
                }
            }
        }
        if(time()!=-1 && time>time()) time=time();
    }
    
    public static void copy() {
        copy = new int[N][N];
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                copy[i][j]=map[i][j];
            }
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<N;
    }
    
    public static void transfer() {
        for(int i=0;i<select.size();i++) {
            queue.add(new info(select.get(i).x, select.get(i).y));
        }
    }
    
    public static int time() {
        int min=0, count=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(copy[i][j]>min) min = copy[i][j];
                if(copy[i][j]==0) count++;
            }
        }
        if(count!=M) return -1;
        
        return min;    
    }
 
}