[코드트리 조별과제] 바이러스 백신

 

문제 : 바이러스 백신

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제는 아래와 같다

N x N 크기의 도시에 병원, 벽, 바이러스가 있고, 

M개의 병원에 백신을 제공할 수 있다.

 

백신이 제공된 병원을 시작으로 매 초마다

상하좌우로 인접한 지역 중 벽을 제외한 지역에 백신이 공급되기 때문에 그 자리에 있던 바이러스 제거

M개의 병원을 적절히 골라 최대한 빨리 바이러스를 없애고자 함

• 3 ≤ n(전체 크기) ≤ 50
• 1 ≤ m(병원의 수) ≤ 10

문제를 봤을 때 전체 x개의 병원 중 m개의 병원을 고른다는 점 에서 조합을매 초마다 상하좌우로 인접한 지역에 백신이 공급된다는 점 에서 BFS가 떠올라서 이를 활용해서 풀었다.

 

그래서 아래와 같은 풀이로 풀었다.

 

입력(input) 함수

1. 병원에 대한 정보를 저장하는 ArrayList<int[]> 타입의 hospitals를 선언 

1-1. int[3]의 요소는 병원의 x, y좌표 그리고 백신이 퍼지는 날짜가 저장

1-2. 백신이 퍼지기 전이므로 초기에는 0일부터 시작

2. 입력값 중 바이러스와 병원의 수를 미리 저장

 

풀이(pro)함수1. 전체 병원 중 m개의 병원을 뽑아야 하므로 재귀(select)함수를 사용해 조합 선택2. 선택된 병원을 가지고 bfs 함수를 사용해 바이러스 제거 로직 실행

2-1. 선택된 병원에 대한 방문 처리

3. bfs를 하며 날짜 갱신, 바이러스를 제거했다면 카운팅

4. bfs가 종료됬을 때 전체 바이러스 숫자와 제거한 바이러스가 같다면 날짜를 갱신

 

시간복잡도를 계산하면

1. 조합O(mC(m/2)) -> 10C5 -> 252

2. bfs O(n^2) -> 50^2 -> 2500

2500 * 252 = 630,000으로 1초 안에 연산이 가능하다.

 

코드는 아래와 같다

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

public class Main {
    
    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    static int[][] map;
    static ArrayList<int[]> hospitals;
    static int virusCnt, hospitalCnt;
    static int n, m;
    static int minDay = Integer.MAX_VALUE;
    
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static boolean[][] visit;
    static Deque<int[]> que;

    public static void main(String[] args) throws IOException{
        input();
        pro();
    }

    static void input() throws IOException{
        
        hospitals = new ArrayList<>();
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[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] == 0) virusCnt++;
                if (map[i][j] == 2) {
                    hospitals.add(new int[] {i, j, 0});
                    hospitalCnt++;
                    continue;
                }
            }
        }
    }

    static void pro() {

        if (virusCnt == 0) {
            System.out.println(0);
            return;
        }
        
        select(0, 0, new ArrayList<int[]>());
        if (minDay == Integer.MAX_VALUE) minDay = -1;
        System.out.println(minDay);
    }

    static void select(int depth, int startIdx, ArrayList<int[]> selectedHospitals) {
        if (depth == m) {
            minDay = Math.min(minDay, bfs(selectedHospitals));
            return;
        }

        for (int i = startIdx; i < hospitalCnt; i++) {
            selectedHospitals.add(hospitals.get(i));
            select(depth + 1, i + 1, selectedHospitals);
            selectedHospitals.remove(depth);
        }
    }

    static int bfs(ArrayList<int[]> selectedHospitals) {
        
        // selectedHospitals는 {r, c, curDay}로 구성된 int[3] 배열
        int day = -1;
        int killedVirus = 0;

        que = new ArrayDeque<>(selectedHospitals);
        visit = new boolean[n][n];
        for (int[] select : selectedHospitals) {
            visit[select[0]][select[1]] = true;
        }
        

        while(!que.isEmpty()) {
            int[] cur = que.pollFirst();
            int curDay = cur[2];
            day = curDay;
            if (killedVirus == virusCnt) continue;

            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];

                if (ny == -1 || nx == -1 || ny == n || nx == n) continue;
                if (visit[ny][nx]) continue;
                if (map[ny][nx] == 1) continue;
                if (map[ny][nx] == 0) killedVirus++;
                visit[ny][nx] = true;
                int[] next = new int[] {ny, nx, curDay + 1};
                que.add(next);
            }
        }
        
        if (killedVirus != virusCnt) day = Integer.MAX_VALUE;
        return day;
    }
}