[백준 14502] 연구소

문제

접근

완전 탐색을 통해서 현재 주어진 맵에서 벽 3개를 세우는 모든 경우의 수를 구해야 한다고 생각했다. -> 백트래킹
경우의 수 별로 바이러스가 퍼진 것을 파악해 안전지대가 최대 크기인 경우를 출력해야 한다고 생각했다.
이 때 바이러스가 퍼진 것은 BFS를 통해서 구현하고자 했다.

풀이

1. 입력 처리 및 초기화:

BufferedReader와 StringTokenizer를 사용하여 입력을 처리하고, 격자 크기(N x M)와 map 배열을 초기화합니다.
map 배열에는 현재 연구소의 상태를 저장하고, tempMap 배열은 바이러스가 퍼졌을 때의 상태를 저장합니다.
벽 설치 (buildWalls 메소드):

2. 3개의 벽을 세우기 위해 백트래킹을 사용합니다.

벽이 3개 설치되면 (count == WALL_COUNT), 바이러스가 퍼지는 상황을 시뮬레이션하는 spreadVirus() 메소드를 호출합니다.
벽을 설치한 후에는 해당 위치를 다시 빈 칸(0)으로 복구하여 다른 조합을 시도합니다. 이를 백트래킹이라고 합니다.

3. 바이러스 퍼뜨리기 (spreadVirus 메소드):

Queue를 사용해 BFS 방식으로 바이러스를 퍼뜨립니다.
map 배열에서 바이러스(2)의 위치를 찾은 후, Queue에 넣어 BFS를 시작합니다.
상하좌우(dx와 dy 배열)를 확인하여 바이러스가 퍼질 수 있는 빈 칸(0)으로 퍼지게 합니다.
안전 영역 계산 (calculateSafeZone 메소드):

4. 바이러스가 퍼진 후, 안전 영역의 크기(빈 칸의 개수)를 계산합니다.

현재까지 계산된 최대 안전 영역(maxSafeZone)과 비교하여 더 큰 값을 저장합니다.

시간 복잡도

이 알고리즘은 가능한 모든 3개의 벽 조합을 탐색하므로, 경우에 따라 시간 복잡도가 높아질 수 있습니다. (백트래킹의 경우 O((N*M)^3)의 시간 복잡도를 가집니다).
N과 M의 최대 값은 8이기 때문에 실행 시간을 초과하지 않습니다.

전체 코드

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

public class Main {
    static int N, M;
    static final int WALL_COUNT = 3;
    static int[][] map;
    static int[][] tempMap;
    static int maxSafeZone = 0;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    public static void main(String[] args) throws Exception {
        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][M];
        tempMap = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        buildWalls(0);
        System.out.println(maxSafeZone);

    }

    private static void buildWalls(int count) {
        if (count == WALL_COUNT) {
            spreadVirus();
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    buildWalls(count + 1);
                    map[i][j] = 0; // 백트래킹 ( 원상 복구)
                }
            }
        }
    }

    private static void spreadVirus() {
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                tempMap[i][j] = map[i][j];
                if (tempMap[i][j] == 2) {  // 바이러스 위치를 큐에 추가
                    q.add(new int[]{i, j});
                }
            }
        }
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (tempMap[nx][ny] == 0) {
                        tempMap[nx][ny] = 2;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
        calculateSafeZone();
    }

    private static void calculateSafeZone() {
        int safeZone = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (tempMap[i][j] == 0) {
                    safeZone++;
                }
            }
        }
        maxSafeZone = Math.max(maxSafeZone, safeZone);
    }
}