[BOJ] 17142. 연구소 3(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

코로나 시대..

문제처럼 바이러스가 퍼지는 것이 아니라 백신이 퍼졌으면 하는 바램이다..

이전 연구소 문제를 풀어보았다면 나름 수월하게 풀 수 있는 문제다.

[BOJ] 14502. 연구소(DFS, DFS).java

동작을 간략하게 정리해보면

1. 조합을 활용하여 비활성 바이러스 중 M개를 활성 상태로 변경해주자.

2. 선택되어 활성 상태가 된 M개의 바이러스는 사방으로 퍼진다.

2-1. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

비활성 바이러스가 활성으로 변하면 바로 사방으로 바이러스가 퍼지게 구현해주어야 한다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ17142 {
    
    static final int max = Integer.MAX_VALUE;
    
    static int N, M, cntSpace, minTime, map[][];
    static List<Point> virusZone;
    static Point[] virus;
    static boolean[][] visited;
    static Queue<Point> q;
    static int[] dr= {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    
    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];
        virus = new Point[M]; // 선택된 활성 바이러스
        virusZone = new ArrayList<>(); // 바이러스를 놓을 수 있는 칸
        
        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) cntSpace++;
                // 바이러스를 놓을 수 있는 공간일 경우
                if(map[i][j] == 2) virusZone.add(new Point(i, j));
            }
        }
        
        minTime = max;
        cntSpace -= M; // 초기 선택된 바이러스는 제외
        process(0, 0);
        
        // 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우
        if(minTime == max) System.out.println(-1);
        else System.out.println(minTime);
    }
    
    private static void process(int cnt, int start) {
        
        // 모든 바이러스를 설치
        if(cnt == M) {
            int time = spreadVirus();
            minTime = Math.min(minTime, time);
            
            return;
        }
                
        for (int i = start; i < virusZone.size(); i++) {
            // 이 구역 바이러스를 활성 상태로
            virus[cnt] = virusZone.get(i);
            
            process(cnt + 1, i + 1);
        }
    }
 
    private static int spreadVirus() {
        
        int cntSpread = 0, time = 0, tmp = 0;
        visited = new boolean[N][N];
        q = new LinkedList<>();
        // 초기 설치된 바이러스의 위치
        for (int i = 0; i < M; i++) {
            q.add(virus[i]);
            visited[virus[i].r][virus[i].c] = true;
        }
 
        // 바이러스 확산
        while(!q.isEmpty()) {
            
            int size = q.size();
            boolean space = false;
            
            while(size-- > 0) {
                Point now = q.poll();
                
                for (int d = 0; d < 4; d++) {
                    int rr = now.r + dr[d];
                    int cc = now.c + dc[d];
                    // 범위를 벗어나면 pass
                    if(rr < 0 || cc < 0 || rr >= N || cc >= N) continue;
                    // 벽이거나 이미 방문한 곳이면 pass
                    if(map[rr][cc] == 1 || visited[rr][cc]) continue;
                    // 빈 칸일 경우
                    if(map[rr][cc] == 0) space = true;
                    // 빈 칸이거나 비활성 바이러스일 경우, 감염시키고 Queue에 add
                    visited[rr][cc] = true;
                    cntSpread++;
                    q.add(new Point(rr,cc));
                }
            }
            
            // 바이러스의 연쇄 확산일 경우
            if(!space) tmp++;
            else {
                time += ++tmp;
                tmp = 0;
            }
        }
        
        // 모든 빈 칸에 바이러스가 퍼졌다면
        if(cntSpread == cntSpace) return time;
        return max;
    }
 
    static class Point {
        int r, c;
 
        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
        
    }
}
 

line 53~69) 조합으로 비활성 바이러스 중 M개를 선택하여 활성 바이러스로 선택

line 56~61) M개의 바이러스를 선택했다면 확산을 시켜보자.

line 63~68) 조합으로 비활성 바이러스를 선택

line 71~118) 바이러스의 확산

line 77~80) 초기 선택된 바이러스를 Queue에 추가해주자.

line 83~113) 바이러스의 확산 과정

line 99) 빈 칸일 경우만 따로 체크를 해주자.

line 101~103) 빈 칸이거나 비활성 바이러스일 경우

방문 체크, 감염된 영역 개수 추가, Queue에 추가

line 108~112) 이 부분이 가장 핵심(?)이다. 하단에 추가 설명

line 116~117) 모든 빈 칸에 바이러스가 퍼졌는지 확인

***

line 108~112) 바이러스가 확산되는데 두 가지 경우가 있다.

1. 연쇄 확산이 일어날 경우

   "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다." 의 동작이

   연쇄적으로 일어날 경우.

2. 평범한 확산이 일어날 경우 (빈칸이 바이러스로 확산되었을 경우)

(1번)의 경우에는 연쇄 확산이 일어나므로 모든 확산이 "동시에" 이루어진다.

한 마디로 동시에 바이러스가 사방으로 퍼져버리는 것이다.

이 부분은 모든 칸이 연쇄 확산으로 바이러스가 퍼질 경우를 예외처리해준 부분이라고 생각하면 된다.

연쇄 확산이 일어날 경우도 사실상 전체로 보았을 때 1초가 걸리는 동작이므로 소요 시간을 따로 관리해주자.

마지막 TC를 보면 연쇄 확산의 의미를 이해하기 쉬울 것이다.

Input

5 1
2 2 2 1 1
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
2 2 2 1 1

     Output

0

(2번) 평범한 확산이 일어날 경우(빈칸이 바이러스로 확산되었다면)

"활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다." 의 상황이 발생하더라도

빈 칸이 한 칸이라도 확산되었다면, 

현재 활성 바이러스가 바로 퍼지나 / 다음 턴에 퍼지나 (어차피 빈 칸(확산된)이 동일한 큐에 존재해서 다음 턴이 와야 함)

동일한 결과를 보인다.

그래서 활성 바이러스로 변한 칸이 있더라도, 빈칸이 하나라도 바이러스로 확산되었다면 그냥 평범한 확산이 일어나게 구현해주면 된다.

line 110) 만일 이전에 연쇄 확산이 일어났었다면 따로 관리해둔 시간을 누적해주자.

* 글로 동작을 설명한다는 것이 정말 어렵다는 것을 다시 한번 깨닫게 되었다..

  누군가 읽더라도 이해가 잘 되었으면 좋겠다.. :(

  그리고.. 코로나 바이러스가 하루빨리 종식되길..