[백준 14502] 연구소 (Java)

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

14502번: 연구소

접근 방법

1. 벽을 3개 세우는 모든 경우를 찾는다. (부르트포스)

  - 벽이 3개가 될 때까지 벽을 세운다.

  - 벽이 3개가 되면 다음 단계로 넘어간다.

  - 다음 단계가 종료되면 다른 경우의 벽 3개를 세운다.

 

2. 벽이 세워진 맵을 복사한다.

  - 원래 맵은 계속해서 사용해야하기 때문에 복사해서 사용해야한다.

  - 맵을 복사할 때는 깊은 복사를 해야한다.

 

3. 복사한 맵에서 바이러스를 우선 확산 시킨다. (바이러스가 퍼질 수 있는 공간을 2로 바꾼다)

 

4. 탐색을 통해 안전 지역(0)의 면적을 구한다.

 

5. 위 순서를 계속해서 반복(벽 3개를 세우는 모든 경우)해 안전 면적의 최대값을 구한다.

 

 

바이러스를 확산시키고 안전 지역의 면적을 구하는 것은 BFS을 이용해 어렵지 않게 구할 수 있었다.

오히려 3개의 벽을 어떻게 세울 것인지를 더 고민했다.

결론은 모든 경우를 탐색하는 부르트포스 방법을 이용하였다. 세부적인 구현은 재귀함수를 이용했다.

 

한 가지 새로 알게 된 것이 있다면 2차원의 깊은 복사 방법이었다.

배열을 복사하고자 할 때 clone()을 사용해야 깊은 복사가 된다고 알고 있어서 잘 구현했다고 생각했는데,

결과가 clone()을 하지 않을 때와 동일하게 나와 알아보니 2차원 이상의 배열의 경우 clone()을 하여도 얕은 복사가 된다는 것을 알게 되었다. 이를 해결하기 위해 2차원 배열의 깊은 복사를 하는 메소드를 추가로 구현해 해결하였다.

 

 

소스 코드

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

public class Main {
    private static int N;
    private static int M;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] cloneMap;
    private static int numberOfWalls = 0;
    private static int[] dx = {1, 0, -1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static int count;
    private static int max = 0;

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

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

        map = new int[N + 1][M + 1];

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

        makeWall();
        System.out.println(max);
    }

	// 부르트포스. 재귀함수를 통해 벽을 3개 세우는 모든 경우의 수 체크함
    private static void makeWall() {
    	// 벽이 3개가 된 경우에 다음 단계로 진입
        if (numberOfWalls == 3) {
            cloneMap = deepCopy(map); // 2차원 배열을 깊은 복사
            visited = new boolean[N + 1][M + 1];
            count = 0;

            // 바이러스를 확산시킴
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (cloneMap[i][j] == 2 && !visited[i][j]) {
                        visited[i][j] = true;
                        bfs2(i, j);
                    }
                }
            }

            // 안전 영역 탐색
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (cloneMap[i][j] == 0 && !visited[i][j]) {
                        visited[i][j] = true;
                        bfs(i, j);
                    }
                }
            }

            max = Math.max(max, count);
        } else {
            // 벽이 3개가 될 때까지 벽을 세움
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (map[i][j] == 0) {
                        numberOfWalls++;
                        map[i][j] = 1;

                        makeWall();

                        // 확인이 된 경우의 수는 다음을 위해 되돌려 놓아야 함
                        numberOfWalls--;
                        map[i][j] = 0;
                    }
                }
            }
        }
    }

    // 2차원 배열을 깊은 복사하는 메서드
    private static int[][] deepCopy(int[][] map) {
        int[][] cloneMap = new int[map.length][];

        for (int i = 0; i < map.length; i++) {
            cloneMap[i] = map[i].clone();
        }

        return cloneMap;
    }

	// 바이러스를 확산시키는 메서드
    private static void bfs2(int x, int y) {
        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(x, y));

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            for (int i = 0; i < 4; i++) {
                int newX = point.x + dx[i];
                int newY = point.y + dy[i];

                if (isInArea(newX, newY) && cloneMap[newX][newY] == 0 && !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    cloneMap[newX][newY] = 2;
                    queue.add(new Point(newX, newY));
                }
            }
        }
    }

	// 안전 지역을 탐색하는 메서드
    private static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(x, y));

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            count++;

            for (int i = 0; i < 4; i++) {
                int newX = point.x + dx[i];
                int newY = point.y + dy[i];

                if (isInArea(newX, newY) && cloneMap[newX][newY] == 2) {
                    return;
                }

                if (isInArea(newX, newY) && cloneMap[newX][newY] == 0 && !visited[newX][newY]) {
                    visited[newX][newY] = true;
                    queue.add(new Point(newX, newY));
                }
            }
        }
    }

    private static boolean isInArea(int x, int y) {
        return x > 0 && y > 0 && x <= N && y <= M;
    }

    static class Point {
        private int x;
        private int y;

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