백준 17142 연구소 3 - JAVA

17142 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static int[][] lab;
    static List<int[]> virus;
    static List<int[]> selectedV;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int minDist = Integer.MAX_VALUE;
    static int zeroCount = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        lab = new int[N][N];
        virus = new ArrayList<>();
        selectedV = new ArrayList<>();
        
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                lab[i][j] = Integer.parseInt(st.nextToken());
                if (lab[i][j] == 2) virus.add(new int[] {i, j});
                if (lab[i][j] == 0) zeroCount++;
            } 
        } 
        combinationVirus(0, 0);
        bw.write(minDist != Integer.MAX_VALUE ? String.valueOf(minDist) : "-1");
        bw.flush();
    }
    private static void combinationVirus(int start, int depth) {
        if (depth == M) {
            int time = bfs();
            if (time != -1) minDist = Math.min(minDist, time);
            return;
        }
        int size = virus.size();
        for (int i = start; i < size; i++) {
            selectedV.add(virus.get(i));
            combinationVirus(i+1, depth+1);
            selectedV.remove(selectedV.size() - 1);
        } 
    }
    private static int bfs() {
        int lastTime = 0;
        if (zeroCount == 0) return 0;
        int empty = zeroCount;
        boolean[][] visited = new boolean[N][N];
        ArrayDeque<int[]> deque = new ArrayDeque<>();
        for (int[] v : selectedV) {
            deque.offer(new int[] {v[0], v[1], 0}); // 거리값이 필요하므로 새로운 배열 만들기
            visited[v[0]][v[1]] = true;
        } 
        while(!deque.isEmpty()) {
            int[] current = deque.poll();
            int x = current[0];
            int y = current[1];
            int dist = current[2];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (visited[nx][ny] || lab[nx][ny] == 1) continue; //이제 비활성 바이러스와 빈칸만 구분
                visited[nx][ny] = true;
                if (lab[nx][ny] == 0) {
                    empty--;
                    lastTime = dist + 1;
                    if (empty == 0) return lastTime;
                }
                deque.offer(new int[] {nx, ny, dist + 1});
            } 
        }
        return -1;
    }
}

 

알고리즘 설명

---

해당 문제는 주어진 비활성 상태의 바이러스 중 M개를 선택하였을 때, 연구실에 바이러스가 전부 퍼지는 최소 시간을 구하는 문제입니다. M개를 선택하는데에 따로 규칙이 없기 때문에 모든 조합을 고려하고, 최소 전파 시간(lastTime)을 구해야 하므로, 너비 우선 탐색으로  모든 경우 중에 최소값을 구해야 합니다. 만약 퍼뜨릴 수 없는 경우 -1을 출력합니다.

empty변수가 0 즉, 모든 연구실이 바이러스가 전부 퍼진 경우 최소 시간 계산을 위한 탐색을 종료 해도 되기 때문에, if 조건을 통해 조기 종료 조건을 추가 합니다.

 

BFS의 경우, Queue 자료구조의 구현체를 LinkedList로 구현하는 경우와, ArrayDeque으로 구현하는 경우의 차이를 살펴보겠습니다.

먼저 자바에서 LinkedList는 이중 연결 리스트(Double LinkedList)의 특징을 가지며 각 원소가 노드의 형태로 연결되어있고, 아래 그림과 같이 한 노드가 이전 노드의 메모리 주소와 다음 노드의 메모리 주소를 참조의 형태로 가지고 있는 자료구조입니다. 따라서 원소의 삽입과 삭제가 빠르지만, 한 노드가 이전 노드와 다음 노드의 참조변수를 가지고 있어야 하기 때문에, 큐가 커질 수록 메모리의 양이 급격히 늘어나게 됩니다. 추가적으로 메모리가 연속적으로 저장되어있지 않아, Cache Locality가 낮아 메모리 사용량 대비 효율이 떨어지는 편입니다.

 

<Double LinkedList>

이번에는 ArrayDeque을 살펴보겠습니다. ArrayDeque은 내부적으로 원형배열(Circular Array)의 형태로 구현이 되어있어 메모리가 연속적이며, 참조변수를 따로 가질 필요가 없습니다. 따라서, 메모리의 사용량이 적고 자료구조안의 원소들이 연속적인 메모리 주소를 사용하기 때문에 Cache Locality가 높아 캐시 효율 및 메모리 효율이 좋습니다.

 

<ArrayDeque>

그래서 BFS 처럼 큐의 연산이 빈번하게 일어나는 경우 ArrayDeque이 일반적으로 더 빠르고 효율적인 구현체임을 알 수 있습니다.

위부터 차례대로 ArrayDeque, LinkedList

위 사진 처럼, 실제로 ArrayDeque으로 큐를 구현한 자료구조가 메모리 사용량이 적은 것을 볼 수 있습니다.

 

코드 해석

---

연구소에서 활성화할 바이러스는 M개로 정해져 있으므로, 모든 바이러스 후보 중에서 M개를 선택하는 조합을 생성합니다. 선택된 조합은 리스트에 저장하며, 각 조합마다 BFS를 수행하여 바이러스가 연구소 전체로 퍼지는 시간을 계산합니다. BFS에서는 큐를 사용하며, 시작점은 선택된 활성 바이러스의 좌표입니다. 각 위치를 탐색할 때 상하좌우로 이동하면서 벽이나 이미 방문한 칸을 제외하고 이동합니다. 빈 칸에 도달하면 lastTime을 갱신하고, 빈 칸 수를 감소시켜 모든 빈 칸에 도달했는지 확인합니다. 만약 빈 칸이 모두 채워지면 BFS를 조기 종료하고 lastTime을 반환합니다.

 

모든 조합에 대해 BFS를 수행하며, 전파 시간이 가능한 값 중 최소값을 갱신합니다. 모든 탐색이 끝난 후, 최소 전파 시간이 존재하면 출력하고, 불가능한 경우에는 -1을 출력합니다.