[백준] 14502 연구소 - JAVA

백준 14502 연구소 GoldIV - JAVA 📌

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

문제 설명

N X M 으로 주어진 배열에서 벽을 3개 세웠을 때, 안전 영역 크기의 최댓값을 구하는 문제

문제 풀이

---

접근 💡

- 벽을 3개 세워야 한다. [2차원 배열을 탐색하면서 벽을 3개 세울 수 있는 모든 경우의 수 고려하기] << 백트래킹 탐색
- 벽이 3개 세워졌을 때 바이러스를 퍼뜨린다. [바이러스를 찾아 (상,하,좌,우)가 0일 때 퍼뜨려야 한다] << BFS
- 바이러스를 퍼뜨린 후 안전 영역의 개수를 카운트 한다. 우리는 안전 영역의 최댓값을 구해야 한다.

즉 벽이 3개 세워진 경우마다 바이러스가 퍼진 후 안전 영역의 개수를 최댓값으로 갱신해주어야 한다.

벽이 3개 세워진 경우의 배열을 bfs() 메서드에서 깊은 복사 해주어야 함!

깊은 복사 / 얕은복사

1. 얕은 복사 : 복사한 배열이 원래 배열의 '주솟값'을 가져온다.

2. 깊은 복사 : 복사한 배열이 원래 배열을 '그대로' (값 자체를) 가져온다.

코드 💡

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 N, M;
    static int[][] graph;
    static int ans;
    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());

        graph = new int[N][M];

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

    }

    // 벽이 3개 세워지는 모든 경우 탐색하기.
    public static void dfs(int depth) {
        if (depth == 3) {
            int count = bfs(); // 벽이 3개 세워 졌을 때 바이러스 퍼뜨리기.
            ans = Math.max(count, ans); //바이러스 퍼뜨린 후 안전영역 최댓값 갱신!
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (graph[i][j] == 0) {
                    graph[i][j] = 1;
                    dfs(depth + 1);
                    graph[i][j] = 0;
                }
            }
        }
    }
    public static int bfs() {
        int[] dr = {0, 0 ,-1, 1};
        int[] dc = {-1, 1, 0, 0};

        int[][] chk = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                chk[i][j] = graph[i][j];
            }
        }
        Queue<int[]> q = new LinkedList<>();
        //바이러스가 존재하는 좌표를 구한 뒤
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (chk[i][j] == 2) {
                    q.offer(new int[] {i, j});
                }
            }
        }
        //바이러스 퍼뜨리기.
        while (!q.isEmpty()) {
            int[] lst = q.poll();
            int cur_r = lst[0];
            int cur_c = lst[1];
            for (int i = 0; i < 4; i++) {
                int nr = cur_r + dr[i];
                int nc = cur_c + dc[i];
                if (nr >= 0 && nr < N && nc >= 0 && nc < M && chk[nr][nc] == 0) {
                    chk[nr][nc] = 2;
                    q.offer(new int[] {nr, nc});
                }
            }
        }

        //bfs() 메서드의 리턴 값을 int로 하여 안전영역인 경우 세어주기.
        //최댓값으로 초기화하기 위하여!!
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (chk[i][j] == 0) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}