[백준] 14502 연구소 / java

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

14502번: 연구소

---

문제 풀이

이 문제는 BFS 카테고리의 문제 목록에서 발견했지만 실상은 BFS와 DFS를 복합적으로 사용해야 하는 문제였다.

각각이 사용되는 부분은 아래와 같다.

• DFS: 벽을 3개 세우는 경우의 수 탐색
• BFS: 위 DFS에서 찾은 각 경우에 대해 바이러스를 퍼뜨리는 과정 탐색

다시 말해, DFS로 BFS를 할 케이스를 골라내는 것이다.

 

더불어 유의할 점으로 Deep Copy와 Swallow Copy의 차이가 있다.

입력으로 받은 데이터는 원본 배열로서 저장하고, 각 그래프 탐색 과정에서는 원본 배열의 변형을 막기 위해 복사된 배열을 사용하는데

copyMap = map 과 같이 얕은 복사를 하게 되면 copyMap의 값을 변경했을 때 원본 배열 map 또한 함께 변경되므로 문제가 생긴다.

따라서 clone() 을 사용하여 Deep Copy를 했다.

*기본형에 대해서는 clone()으로 깊은 복사가 가능하지만, 참조형에 대해서는 불가능하다.

 

추가적인 설명은 소스코드의 주석으로 이어진다.

소스 코드

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ14502 {
    static int N;  // 지도의 세로 길이
    static int M;  // 지도의 가로 길이
    static int[][] map;  // 원본 배열
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int maxSafeZone = Integer.MIN_VALUE;  // 안전지역 갯수의 최댓값

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        dfs(0);

        System.out.println(maxSafeZone);
    }

    // 벽 3개를 세울 수 있는 모든 경우 dfs 탐색
    // 그리고 조건(wallCnt == 3)을 만족하는 모든 각 dfs 경우에 대해 bfs 탐색
    static void dfs(int wallCnt) {
        // 벽 3개가 모두 설치된 경우 bfs 출발
        if (wallCnt == 3) {
            bfs();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    dfs(wallCnt+1);
                    map[i][j] = 0;  // 다른 dfs에 영향을 주지 않기 위해 원본 배열 map의 값을 다시 원래대로 돌려놓는다
                }
            }
        }
    }

    static void bfs() {
        Queue<Node> q = new LinkedList<>();

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

        int[][] copyMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            copyMap[i] = map[i].clone();  // 원본 배열의 변형을 막기위해 deep copy 사용
        }

        while (!q.isEmpty()) {
            Node cur = q.poll();
            int x = cur.x, y = cur.y;

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

                // 새로운 위치가 map의 범위 내에 있어야 한다
                if (nx >= 0 && ny >= 0 && nx <= N-1 && ny <= M-1) {
                    if (copyMap[nx][ny] == 0) {
                        q.add(new Node(nx, ny));
                        copyMap[nx][ny] = 2;
                    }
                }
            }
        }

        // safeZone의 갯수 탐색하여 최댓값 갱신
        checkSafeZone(copyMap);
    }

    static void checkSafeZone(int[][] copyMap) {
        int safeZoneCnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copyMap[i][j] == 0) {
                    safeZoneCnt++;
                }
            }
        }

        // 최댓값 갱신
        if (maxSafeZone < safeZoneCnt) {
            maxSafeZone = safeZoneCnt;
        }
    }

    static class Node {
        int x;
        int y;

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

}