[백준/Java] 14502 - 연구소

14502 - 연구소

문제 바로가기

문제

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

요구사항

• 목표: $N \times M$ 크기의 연구소에 바이러스(2)가 유출되었다. 바이러스는 상하좌우 빈 칸(0)으로 퍼져나간다. 벽(1)을 정확히 3개 새로 세워서 바이러스가 퍼지는 것을 막고, 안전 영역(Safe Area)의 크기를 최대로 만들어야 한다.
• 제약 조건:
  • 지도의 세로($N$), 가로($M$) 크기는 $3 \le N, M \le 8$이다.
  • 벽의 개수는 3개여야 하며, 빈 칸에만 세울 수 있다.
  • 시간 제한은 2초이다.

접근 방식

이 문제는 완전 탐색(Brute Force)과 너비 우선 탐색(BFS)이 결합된 유형이다.
연구소의 크기가 최대 $8 \times 8 = 64$칸으로 매우 작기 때문에, 벽을 세울 수 있는 모든 경우의 수를 확인해도 시간 내에 통과할 수 있다.

핵심 로직

1. 조합 (Combination): 빈 칸 중 3곳을 골라 벽을 세운다.
2. BFS (Virus Spread): 벽이 세워진 상태에서 바이러스를 퍼뜨린다.
3. 안전 영역 계산: 바이러스가 퍼지지 않은 빈 칸의 개수를 세고, 최댓값을 갱신한다.

🛠️ 최적화 포인트 (Optimization)

1. 2차원 배열의 1차원 인덱스 변환
보통 2차원 배열에서 조합을 구할 때 2중 for문과 복잡한 인덱스 처리를 사용하기 쉽다. 하지만 $N \times M$ 크기의 2차원 배열을 $0$부터 $N \times M - 1$까지의 1차원 배열로 생각하면 로직이 훨씬 간결해진다.

• 행(Row): i / M
• 열(Col): i % M
• start 인덱스를 인자로 넘겨주어 중복 탐색을 방지한다.

2. 안전 영역 카운팅 $O(1)$
BFS가 끝날 때마다 전체 배열을 다시 순회하며 0을 세면 비효율적이다.

• 처음에 전체 빈 칸의 개수(initialEmptySpace)를 미리 세둔다.
• 벽 3개를 세웠으므로 기본 안전 영역은 initialEmptySpace - 3이다.
• BFS 도중 바이러스가 퍼질 때마다(value--) 안전 영역을 하나씩 줄이면, 탐색 종료 후 별도의 카운팅 없이 바로 결과를 얻을 수 있다.

3. 시간 복잡도 분석

• 조합: 최대 64칸 중 3개를 뽑는 경우의 수 $\approx$ $_{64}C_3 = 41,664$
• BFS: 정점(64) + 간선($64 \times 4$) 탐색 $\approx O(NM)$
• 총 연산: $41,664 \times 64 \approx 2.6 \times 10^6$ (약 260만 번)
• 제한 시간 2초(약 2억 번 연산) 대비 1~2% 수준이므로 매우 넉넉하다.

코드

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

class Point {
    int x;
    int y;

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

public class Main {
    static ArrayList<Point> al;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];
        al = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 2) al.add(new Point(i, j));
            }
        }

        comb(arr, 0, 0, n, m);
        System.out.println(answer);

    }

    static int bfs(int[][] arr, int n, int m) {
        int value = 0;
        int[][] tmp = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tmp[i][j] = arr[i][j];
                if(tmp[i][j] == 0) value++;
            }
        }
        Queue<Point> q = new LinkedList<>();
        for (Point p : al) {
            q.offer(new Point(p.x, p.y));
        }

        while (!q.isEmpty()) {
            Point now = q.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 >= m) continue;
                if (tmp[nx][ny] == 0) {
                    tmp[nx][ny] = 2;
                    value--;
                    q.offer(new Point(nx, ny));
                }
            }
        }

        return value;
    }

    static void comb(int[][] arr, int cnt, int start, int n, int m) {
        if (cnt == 3) {
            int value = bfs(arr, n, m);
            answer = Math.max(answer, value);
        } else {
            for (int i = start; i < n * m; i++) {
                int x = i / m;
                int y = i % m;

                if(arr[x][y] == 0) {
                    arr[x][y] = 1;
                    comb(arr, cnt + 1, i + 1, n, m);
                    arr[x][y] = 0;
                }

            }
        }
    }
}

느낀점

1. 인덱스 계산의 중요성 (/ vs %) 처음에 1차원 인덱스를 2차원으로 변환할 때 int y = i * m이라고 작성하여 ArrayIndexOutOfBounds 에러가 났다. 행(Row)은 몫(i / m)이고, 열(Col)은 나머지(i % m)라는 기본 공식을 헷갈리지 말자.

2. 큐(Queue)의 초기화 초반 구현에서 Queue를 전역 변수(static)로 선언하고 한 번만 값을 넣은 뒤 계속 재사용했다. 그랬더니 첫 번째 시뮬레이션 이후 큐가 비어버려 바이러스가 퍼지지 않는 오류가 있었다. BFS는 매 호출마다 새로운 큐를 생성하고 바이러스 초기 위치를 다시 넣어줘야 한다는 점을 명심해야겠다.

3. 1차원 조합의 강력함 2차원 배열 조합 문제를 풀 때마다 이중 for문 처리가 까다로웠는데, start 인덱스 하나로 관리하는 방식을 익히니 코드가 훨씬 깔끔해지고 속도도 빨라졌다. 앞으로 2차원 배열 완전 탐색 문제에서는 이 패턴을 적극 활용해야겠다.