[ 백준 17142 ] 연구소 3 ( 자바 )

[ 백준 17142 ] 연구소 3 ( java )

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

 

 

 

 

출처: 백준 코딩 테스트 연습, https://www.acmicpc.net/problem/17142

17142번: 연구소 3

 

 

 

 

 

 

 

 

핵심 

1 dfs를 이용하여 M개의 바이러스 선택하기 

지도 정보를 입력 받을 때, 미리 viruses[바이러스 수][2] 에 따로 바이러스 위치를 저장했다. 

그리고, dfs를 이용하여 활성화 할 M개의 바이러스를 선택했다. 이 때, boolean[] selectedVirus를 이용하여 활성화할 바이러스인지 아닌지를 선택했다. 

 

 

 

 

 

 

2. bfs로 바이러스 퍼뜨리기 

큐를 이용한 전형적인 bfs 인데, 지도가 빈 공간이거나 비활성 바이러스인 곳에 퍼지게 했다. 큐에는 위치 정보를 갖고 있는 Virus객체를 저장했다. 그리고 전형적인 visited 배열 대신 spreadTime 이라는 배열로 재방문을 막으면서 최소 시간을 기록했다. 

 

 

 

 

 

 

3 최소 시간 찾기 

매 dfs에서 spreadTime에서 가장 오래 걸린 시간 중 가장 작은 값이 답이다. 이 때, 바이러스 퍼지는 것이 불간으하면 -1 출력하는 것 주의해야 한다. 이 때, spreadTime시간을 비교할 때, map에서 0인 곳에서의 시간만을 비교해야 한다. 

 

 

 

 

 

4 주의 

활성화 바이러스를 비활성화로 굳이 만들지 않아도 바이러스가 모두 퍼질 수 있는 케이스를 주의해야한다. 

그러기 위해서, 0인 부분에서의 최소 시간만 고려했다. 

 

 

 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요! 

 

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        o_map = new int[N][N];
        c_map = new int[N][N];
        spreadTime = new int[N][N];
        
        // selectedVirus[i][2]; i번째 바이러스의 y, x 저장 
        viruses = new int[10][2];
        vCnt = 0;
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < N ; j++) {
                o_map[i][j] = Integer.parseInt(st.nextToken());
                if(o_map[i][j] == 2) {
                    viruses[vCnt][0] = i;
                    viruses[vCnt][1] = j;
                    vCnt++;
                }
            }
        }
        
        selectedVirus = new boolean[vCnt];
        selectVirus(0, 0);
        if(minAns != Integer.MAX_VALUE)
            System.out.println(minAns);
        else
            System.out.println(-1);
        
    }
    static int N, M, vCnt;
    static int[][] o_map, c_map;
    static int[][] viruses;
    
    static int[][] spreadTime;
    static boolean[] selectedVirus;
    static int minAns = Integer.MAX_VALUE;
    static void selectVirus(int si, int cnt) {
        if(cnt == M) {
            
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j < N ; j++) {
                    c_map[i][j] = o_map[i][j];
                    spreadTime[i][j] = Integer.MAX_VALUE;
                }
            }
            
            Queue<Virus> q = new LinkedList<Virus>();
            for( int i = 0 ; i < vCnt ; i++ ) {
                if(selectedVirus[i]) {
                    q.add(new Virus(viruses[i][0], viruses[i][1]));
                    spreadTime[viruses[i][0]][viruses[i][1]] = 0;
                    c_map[viruses[i][0]][viruses[i][1]] = 1;
                }
            }
            
            Virus cur;
            int ny, nx;
            while(!q.isEmpty()) {
                cur = q.poll();
                for(int dir = 0 ; dir < 4 ; dir++) {
                    ny = cur.y + delta[dir][0];
                    nx = cur.x + delta[dir][1];
                    if(!(ny>=0 && ny < N &&  nx >= 0 && nx < N))
                        continue;
                    // 0 또는 2인 곳에 시간을 모두 작성 
                    if(c_map[ny][nx] != 1 && spreadTime[ny][nx] == Integer.MAX_VALUE) {
                        spreadTime[ny][nx] = spreadTime[cur.y][cur.x]+1;
                        q.add(new Virus(ny, nx));
                    }
                }
            }
            
            int max = 0;
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j < N ; j++) {
                    if(c_map[i][j] != 0)
                        continue;
 
                    if(spreadTime[i][j] == Integer.MAX_VALUE)
                        return;
                    // 0 인 공간 중 가장 큰 시간 찾기 
                    if(max < spreadTime[i][j])
                        max = spreadTime[i][j];
                }
            }
            
            if(minAns > max) {
                minAns = max;
            }
            
            return;
        }
        
        if(si == vCnt) {
            return;
        }
        
        selectedVirus[si] = true;
        selectVirus(si+1, cnt+1);
        
        selectedVirus[si] = false;
        selectVirus(si+1, cnt);
    }
    
    static class Virus{
        int y, x;
        public Virus(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    
    static int[][] delta = {
            {-1, 0},
            {0, 1},
            {1, 0},
            {0, -1}
    };
}