[자바] BOJ_14502_연구소_G5

동동주·2025년 12월 1일

코딩테스트

목록 보기

7/16

🧪 BOJ 14502 연구소

문제 요약

연구소에서 0(빈 칸), 1(벽), 2(바이러스)가 주어진다.
빈 칸 중 3곳을 벽으로 설치한 뒤, 모든 바이러스가 퍼지고 난 뒤
안전 영역(0의 개수)의 최대값을 구하는 문제.

핵심 조건

벽은 정확히 3개 세워야 한다.
바이러스는 상하좌우로 퍼진다.
N, M ≤ 8 → 전체 칸 64칸 이하 → 완전탐색 가능.

풀이 전략

1️⃣ 3개의 벽을 세울 모든 조합 탐색

“3개를 고르는 모든 조합” = 완전탐색
중복 조합 제거 필요 → start 인덱스 기반 탐색
선택 → 재귀 → 취소 패턴이 필수 => 전형적인 백트래킹 구조

2️⃣ BFS로 바이러스 확산 시뮬레이션

tmpArr에 arr을 복사
바이러스(2) 위치를 큐에 모두 담아 BFS 수행
현재 조합에서 안전 영역 계산 → 최댓값 갱신

시간 복잡도 분석

최대 빈칸 수

N, M ≤ 8 → 64칸
모든 칸이 빈칸일 때
→ 벽 3개를 세우는 조합
$\binom{64}{3} = 41,664$

각 조합에서 수행하는 연산

BFS는 최대 64칸 전체를 한 번씩 방문 → O(64)
안전영역 계산도 O(64)

즉 조합 1개당 약 O(64)

전체 시간

$O\left(\binom{64}{3} \times 64\right) \approx O(2.6 \times 10^6)$

약 260만 연산 → Java 2초 제한 충분히 통과(넉넉)
(일반적으로 자바는 1억 연산 ≈ 약 1초로 잡는다.)

➡ 2.6M은 전체 제한 2초에서 1/40도 안 되는 수준.

✅ 최종 코드 (Java)

package algo.ct.M12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_14502_연구소_G5 {
    static int N, M;
    static int[][] arr;
    static int[][] tmpArr;
    static int maxSafe = 0;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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());
        arr = new int[N][M];

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

        setWall(0);
        System.out.println(maxSafe);
    }

    // 3개의 벽을 세우는 백트래킹
    static void setWall(int count) {
        if (count == 3) {
            getVirus();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) {
                    arr[i][j] = 1;
                    setWall(count + 1);
                    arr[i][j] = 0;
                }
            }
        }
    }

    // BFS로 바이러스 확산
    static void getVirus() {
        tmpArr = new int[N][M];

        // 배열 복사
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                tmpArr[i][j] = arr[i][j];

        Queue<int[]> q = new LinkedList<>();

        // 바이러스 위치 큐에 추가
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (tmpArr[i][j] == 2) {
                    q.add(new int[]{i, j});
                }
            }
        }

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

            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d];
                int ny = cur[1] + dy[d];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (tmpArr[nx][ny] != 0)
                    continue;

                tmpArr[nx][ny] = 2;
                q.add(new int[]{nx, ny});
            }
        }

        // 안전 영역 계산
        int safe = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (tmpArr[i][j] == 0) safe++;

        maxSafe = Math.max(maxSafe, safe);
    }
}