[백준] 17141번 - 연구소 2 [Java]

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

 

[백준] 17141번 - 연구소 2 [Java]

[백준] 17141번 - 연구소 2 [Java]

[백준] 17141번 - 연구소 2 [Java]

[백준] 17141번 - 연구소 2 [Java]

[백준] 17141번 - 연구소 2 [Java]

---

1.  아이디어

 

이전 연구소 문제에서 이제 바이러스를 놓을 수 있는 칸 중 바이러스를 M개 놓고 모든 위치에 바이러스를 퍼트릴 수 있는 최소 시간을 구하는 문제로 조합을 통해 바이러스를 퍼트릴 위치를 정한 후 최단거리 BFS를 통해 바이러스가 모두 퍼졌으면 최단거리를 반환하는 방식으로 해결했다.([코딩테스트 준비/백준] - [백준] 14502번 - 연구소 [Java])

---

2. 문제풀이

 

빈칸 없이 바이러스가 퍼졌는지 알기 위해 벽의 개수를 wallCnt로 저장하고 바이러스를 놓을 수 있는 칸을 리스트로 저장했다. 이후 리스트에 대한 조합을 구해서 최단거리 BFS를 수행 후 이를 현재까지 구한 최단 시간과 비교 갱신하는 방식으로 구현했다. 최단거리 BFS는 바이러스가 존재하는 칸의 수와 최단거리를 계산하며 바이러스가 존재하는 칸의 수가 맵의 크기 - 벽의 개수일 때는 최단거리를 반환하고 아니면 -1을 반환해 바이러스가 모두 퍼지지 않았음을 표시했다.

---

3. 코드

 

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

public class Main {

    private static class Node {
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    private static final int WALL = 1;
    private static final int VIRUS = 2;

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    private static final List<Node> virusList = new ArrayList<>();
    private static Node[] sel;

    private static int N;
    private static int M;
    private static int[][] map;

    private static int wallCnt = 0;
    private static int min = Integer.MAX_VALUE;

    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());

        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] == WALL) wallCnt++;
                else if (map[i][j] == VIRUS) virusList.add(new Node(i, j));
            }
        }

        sel = new Node[M];

        combination(0, 0);

        if (min == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(min);
    }

    private static void combination(int idx, int selIdx) {
        if (selIdx == sel.length) {
            boolean[][] visited = new boolean[N][N];
            int dist = bfs(sel, N, map, visited);

            if (dist == -1) return;

            min = Math.min(min, dist);
            return;
        }

        for (int i = idx; i < virusList.size(); i++) {
            sel[selIdx] = virusList.get(i);
            combination(i + 1, selIdx + 1);
        }
    }

    private static int bfs(Node[] start, int N, int[][] map, boolean[][] visited) {
        Queue<Node> q = new ArrayDeque<>(Arrays.asList(start));

        for (Node node : start) {
            visited[node.r][node.c] = true;
        }

        int cnt = M;
        int dist = 0;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                Node node = q.remove();

                for (int dir = 0; dir < 4; dir++) {
                    int nr = node.r + dr[dir];
                    int nc = node.c + dc[dir];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                    if (map[nr][nc] == WALL || visited[nr][nc]) continue;

                    q.add(new Node(nr, nc));
                    visited[nr][nc] = true;
                    cnt++;
                }
            }

            dist++;
        }

        if (cnt == N * N - wallCnt) return dist - 1;
        return -1;
    }

}

---

4. 후기