[백준 JAVA] 14502. 연구소

문제 링크

---

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

접근 방법

---

1. 세울 수 있는 모든 조합으로 벽을 만듭니다 (브루트 포스).
   이때, 세웠던 조합으로 다시 세우지 않도록 합니다.
2. 벽 3개를 세울 때마다 바이러스를 퍼뜨립니다. 

소스 코드

---

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

public class Main {

    static List<int[]> virus = new LinkedList<>(); // 바이러스의 위치를 저장하는 리스트
    static int[] dy = {0, 0, -1, 1}, dx = {1, -1, 0, 0};
    static int[][] map;
    static int y, x, max = 0, safe = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        y = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        map = new int[y][x];
        
        for (int i = 0; i < y; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < x; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2) {
                    virus.add(new int[]{i, j}); // 바이러스 위치를 리스트에 추가
                } else if (map[i][j] == 0) {
                    ++safe; // 빈 칸이 곧 안전 영역이 될 수 있는 공간이므로 미리 셈
                }
            }
        }

        safe -= 3; // 벽 3개를 세울 것이므로, 안전 영역에서 3을 뺌
        crystallize(0, 0, 0);
        System.out.println(max);
    }

    static void crystallize(int cury, int curx, int idx) {
        if (idx == 3) {
            spread(); // 벽 3개를 모두 세운 경우, 바이러스 확산
            return;
        }

        // 연구소의 모든 칸을 순회하며 벽을 세움
        // 세웠던 조합으로 벽을 세우지 않도록 함
        while (cury < y) {
            while (curx < x) {
                if (map[cury][curx] == 0) {
                    map[cury][curx] = 1; // 빈 칸인 경우 벽을 세움
                    crystallize(cury, curx + 1, idx + 1);
                    map[cury][curx] = 0; // 원래 상태로 복구
                }

                ++curx;
            }

            curx = 0; // 다음 행 첫 번째로 이동
            cury++;
        }
    }

    static void spread() {

        Queue<int[]> q = new LinkedList<>(); // y x
        boolean[][] v = new boolean[y][x];
        int cnt = 0; // 바이러스가 퍼진 빈 칸의 수

        q.addAll(virus); // 초기 바이러스 위치를 큐에 추가하고 방문 처리
        for (int[] tmp : virus) {
            v[tmp[0]][tmp[1]] = true;
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                if (ny < 0 || ny == y) {
                    continue;
                }

                int nx = cur[1] + dx[i];
                if (nx < 0 || nx == x || map[ny][nx] != 0 || v[ny][nx]) {
                    continue;
                }

                ++cnt;
                v[ny][nx] = true;
                q.add(new int[]{ny, nx});
            }
        }

        cnt = safe - cnt; // 안전 영역의 크기를 계산
        max = (max > cnt) ? max : cnt; // 최대 안전 영역 크기 갱신
    }
}

코드 설명

---

빈칸에서 세울 3개의 벽을 미리 제외한 후, 그 값을 안전 영역의 최댓값으로 설정합니다.

재귀적으로 벽을 세우는 모든 조합을 탐색하며, 중복되지 않도록 합니다.

벽 3개를 모두 세우면, 바이러스 확산을 시뮬레이션하기 위해 spread 함수를 호출합니다.

이 함수에서는 BFS를 이용해 바이러스가 확산되는 과정을 시뮬레이션합니다.

초기 바이러스 위치들을 큐에 넣고, visited 배열을 사용해 방문 여부를 기록합니다.

바이러스가 퍼진 빈칸의 수를 계산한 후, 현재 조합에서의 안전 영역 크기를 구해 최댓값을 갱신합니다.