[BOJ]14502 - 연구소(G4)

문제 링크

14502-연구소

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.

출력

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

문제 풀이

우선 3개의 벽을 세워야하는데, 모든 칸에 대해서 빈칸인지 확인하고 세워야하기 때문에 dfs 방식 이용
이후에는 전체 영역을 돌면서 안전 영역의 크기를 구해 최대값을 구하는 방식으로 bfs 방식 이용

이 문제에서 놓칠 수 있는 부분은 배열 복사 부분이다.
배열 원본을 변경하지 않으면서 복사된 배열을 사용해야하기 때문에 조심해야한다.

a=b와 같은 대입연산자를 사용하면 얕은 복사가 생겨 원본 배열에 영향을 끼치기때문에 깊은 복사를 이용해야한다.

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 Main {
    static int[][] maps, mapsCopy;
    static int N, M, cnt, maxCnt = Integer.MIN_VALUE;
    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());

        maps = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                maps[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0);
        System.out.println(maxCnt);
    }

    public static void dfs(int depth) {
        if (depth == 3) {
            bfs();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (maps[i][j] == 0) {
                    maps[i][j] = 1;
                    dfs(depth + 1);
                    maps[i][j] = 0;
                }
            }
        }
    }

    public static void bfs() {
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (maps[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        mapsCopy = new int[N][M];
        for (int i = 0; i < N; i++) {
            mapsCopy[i] = maps[i].clone();
        }

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (mapsCopy[nx][ny] == 0) {
                    queue.add(new int[]{nx, ny});
                    mapsCopy[nx][ny] = 2;
                }
            }
        }
        getSafeZone();
    }


// 안전 영역 크기 구하기
    public static void getSafeZone() {
        cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (mapsCopy[i][j] == 0) cnt++;
            }
        }
        maxCnt = Math.max(cnt, maxCnt);
    }
}