BOJ 2234 성곽

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

문제

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

---

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

---

출력

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

---

예제 입력 1

7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

예제 출력 1

5
9
16

---

코드

이번 문제는 BFS 문제이고, 각 방의 벽 정보를 알기 위해 비트마스킹을 사용하는 문제이다.

구해야 하는 것은 세 가지가 있지만, 결국 마지막 세 번째 결과를 구하는 과정에서 1, 2번 결과는 자동으로 구해진다.

전체적으로 구현에 시간이 걸렸다.

풀이 과정은 다음과 같다.

1. BFS로 블럭들을 탐색하며 각 블럭에 방 번호를 매긴다.
2. 방 넓이를 저장하는 ArrayList에 BFS로 탐색하며 구한 방의 넓이를 저장

   이때, ArrayList의 size()로 첫 번째 결과인 방의 수를 구할 수 있고, ArrayList 중 가장 큰 값으로 두 번째 결과인 가장 큰 방의 넓이를 구할 수 있다.

3. 모든 블럭을 탐색하며 벽을 허물었을 때, 합쳐지는 두 개의 방의 크기를 더해서 세 번째 결과를 구하고, 결과들을 출력한다.

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;

public class Main {

    // 서, 북, 동, 남
    static final int[] DIR_ROWS = {0, -1, 0, 1};
    static final int[] DIR_COLS = {-1, 0, 1, 0};

    static int N;
    static int M;
    static int[][] walls; // 각 블럭의 벽 정보를 저장하는 이차원 배열
    static int[][] roomNumbers; // 각 블럭의 방 번호를 저장하는 이차원 배열
    static List<Integer> roomSizes = new ArrayList<>(); // 방 번호에 따른 방의 넓이를 저장하는 List

    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());
        walls = new int[M][N];
        roomNumbers = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                walls[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        checkRooms();
        int maxRoomSize = Collections.max(roomSizes);
        int newMaxRoomSize = calculateNewMaxRoomSize(maxRoomSize);

        StringBuilder answer = new StringBuilder();
        answer.append(roomSizes.size() - 1).append('\n');
        answer.append(maxRoomSize).append('\n');
        answer.append(newMaxRoomSize);

        System.out.println(answer);
    }

    /**
     * 각 블럭에 방 번호를 매기고, 각 방마다 방의 넓이를 계산하는 메소드
     */
    static void checkRooms() {
        roomSizes.add(0); // 방 번호가 1부터 시작하기 때문에 index 0 생략하기 위함
        int roomNumber = 1;

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                // 아직 방 번호를 매기지 않은 블럭일 경우
                // 해당 방에 속한 블럭들에 방 번호를 부여하고, 방의 넓이를 계산
                if(roomNumbers[i][j] == 0) {
                    int roomSize = checkRoomSize(i, j, roomNumber);
                    roomSizes.add(roomSize);
                    roomNumber++;
                }
            }
        }
    }

    /**
     * 블럭들을 BFS로 탐색하며 블렉들에 방 번호를 부여하고, 방의 넓이를 계산
     * @param r 탐색을 시작할 블럭의 행
     * @param c 탐색을 시작할 블럭의 열
     * @param roomNumber 부여할 방 번호
     * @return 방의 넓이
     */
    static int checkRoomSize(int r, int c, int roomNumber) {
        int roomSize = 1;
        Queue<Point> queue = new ArrayDeque<>();
        queue.offer(new Point(r, c));
        roomNumbers[r][c] = roomNumber;

        while (!queue.isEmpty()) {
            Point check = queue.poll();
            int wall = walls[check.x][check.y];

            for (int i = 0; i < 4; i++) {
                // 해당 방향에 벽이 없을 경우, 탐색 진행
                if((wall & 1 << i) == 0) {
                    Point newP = calculateMovablePoint(check.x, check.y, i);

                    if(newP != null && roomNumbers[newP.x][newP.y] == 0) {
                        roomNumbers[newP.x][newP.y] = roomNumber;
                        queue.offer(newP);
                        roomSize++;
                    }
                }
            }
        }

        return roomSize;
    }

    /**
     * 특정 방향으로 한 칸 이동한 위치를 계산하는 메소드
     * @param r 현재 위치한 블럭의 행
     * @param c 현재 위치한 블럭의 열
     * @param dir 이동할 방향
     * @return 이동한 위치
     */
    static Point calculateMovablePoint(int r, int c, int dir) {
        Point newP = new Point(r + DIR_ROWS[dir], c + DIR_COLS[dir]);

        // 성곽 밖의 장소일 경우
        if(newP.x < 0 || newP.x >= M || newP.y < 0 || newP.y >= N) {
            return null;
        }

        return newP;
    }

    /**
     * 벽을 1개 부쉈을 때 가장 큰 방의 넓이를 계산하는 메소드
     * @param maxRoomSize 기존 방 중에서 가장 큰 넓이
     * @return 벽을 1개 부쉈을 때 가장 큰 방의 넓이
     */
    static int calculateNewMaxRoomSize(int maxRoomSize) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                int wall = walls[i][j];
                int roomNumber = roomNumbers[i][j];

                for (int k = 0; k < 4; k++) {
                    // 해당 방향에 벽이 있을 경우, 벽을 허물었을 때의 방 넓이 계산
                    if((wall & 1 << k) != 0) {
                        Point newP = calculateMovablePoint(i, j, k);

                        if(newP != null && roomNumber != roomNumbers[newP.x][newP.y]) {
                            int newRoomSize = roomSizes.get(roomNumber) + roomSizes.get(roomNumbers[newP.x][newP.y]);
                            maxRoomSize = Integer.max(maxRoomSize, newRoomSize);
                        }
                    }
                }
            }
        }

        return maxRoomSize;
    }
}