[백준 17141 : JAVA] 연구소 2 / BFS + 조합

문제

---

 

 

 

풀이

---

먼저 바이러스를 놓을 수 있는 k개의 위치 중 m개의 위치를 선정해야 한다. 이는 조합 ${}_k \mathrm{ C }_m$으로 나타낼 수 있다.

 

조합 알고리즘을 통해 m개의 시작 지점을 정한 후에는 BFS 탐색을 통해 m개의 시작 지점에 대한 탐색을 진행한다.

 

만약, 해당 조합의 시작 지점이 이전 조합의 시작 지점보다 탐색 시간이 길다면 해당 조합은 패스한다.

 

 

 

코드

---

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, M, count = 0, answer = Integer.MAX_VALUE;
    private static int[][] map;
    private static boolean[] check;
    private static List<Node> virus = new ArrayList<>();
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};

    private static class Node {
        int x, y;

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

    public static void main(String[] args) throws Exception {
        StringTokenizer 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] == 2) virus.add(new Node(j, i));
                if (map[i][j] == 0) count++;
            }
        }

        count += virus.size() - M;
        check = new boolean[virus.size()];

        if (count == 0) answer = 0;
        else combination(0, 0);

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

    private static void combination(int depth, int start) {
        if (depth == M) {
            int[][] copyMap = copy();
            bfs(copyMap, count);
            return;
        }

        for (int i = start; i < virus.size(); i++) {
            check[i] = true;
            combination(depth + 1, i + 1);
            check[i] = false;
        }
    }

    private static void bfs(int[][] map, int count) {
        Queue<Node> queue = new LinkedList<>();

        for (int i = 0; i < virus.size(); i++) {
            if (check[i]) queue.add(virus.get(i));
        }

        int time = 0;
        while (!queue.isEmpty()) {
            if (answer <= time) break; // 해당 조합은 이전 조합보다 느리다는 뜻.

            int len = queue.size();
            for (int t = 0; t < len; t++) { // 시작 지점이 여러 개이기 때문에 반복문으로 한 번더 감싼다.
                Node now = queue.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) continue;
                    if (map[ny][nx] != 0) continue;

                    map[ny][nx] = 2;
                    queue.add(new Node(nx, ny));
                    count--; // 지날 수 있는 길 -1
                }
            }

            time++;
            if (count == 0) { // 더이상 지날 수 있는 길이 없다면 (탐색 가능한 길이 없다면)
                answer = time;
                return;
            }
        }
    }

    private static int[][] copy() {
        int[][] copyMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                copyMap[i][j] = (map[i][j] == 2 ? 0 : map[i][j]);
        }

        for (int i = 0; i < virus.size(); i++) {
            if (check[i]) {
                Node node = virus.get(i);
                copyMap[node.y][node.x] = 2;
            }
        }

        return copyMap;
    }
}