[Baekjoon] 백준 2234번: 성곽 (JAVA)

문제 2234번

2234번: 성곽

[ 문제 풀이 ]

1) 방의 개수 / 가장 넓은 방의 넓이 구하기
이 문제에서 벽에 대한 정보를 얻기 위해서는 비트 연산을 이용해야 합니다. 각 4방향(서, 북, 동, 남)이 2^0, 2^1, 2^2, 2^3으로 더해지기 때문에, &와 << 연산자를 사용하여 현재 위치에서 벽이 없는 방향으로 이동하며 방의 개수와 각 방의 넓이를 카운트하면 됩니다.

여기서 주의해야할 점은 int[] moveR, int[] moveC의 순서를 서, 북, 동, 남으로 해주어야 합니다. 비트 연산을 할 때 2^0부터 2^4까지 차례대로 올라가기 때문에 그에 맞게 배열값을 초기화해주어야 현재 위치에서 서, 북, 동, 남 방향으로 벽의 유무를 확인할 수 있게 됩니다.

4방향 위치

 

2) 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 구하기
각 방에 그룹 번호를 붙여 walls[0]에 저장하고, walls[1]에는 이어진 방들의 개수를 각 방마다 저장합니다. walls를 기준으로 현재 위치에서 서, 북, 동, 남을 살펴 id가 다른 경우 벽을 깨면, 서로 다른 그룹의 방을 합칠 수 있는 경우가 생기므로 walls[1]을 더한 값이 최대값인지 확인해주면 됩니다.

문제에 나와있는 예시에 대한 walls[0]과 walls[1]의 모습은 아래와 같습니다.

walls[0]

0	0	1	1	3	3	3
0	0	0	1	3	4	3
0	0	0	2	3	2	3
0	2	2	2	2	2	3

walls[1]

9	9	3	3	8	8	8
9	9	9	3	8	1	8
9	9	9	7	8	7	8
9	7	7	7	7	7	8

 

[ 코드 ]

import org.w3c.dom.Node;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int N, M;
    private static int[][] map;
    private static boolean[][] visit;
    private static int[][][] walls; // 벽의 개수
    // 서, 북, 동, 남
    private static int[] moveR = {0, -1, 0, 1};
    private static int[] moveC = {-1, 0, 1, 0};
    private static int maxRoom = 0; // 가장 넓은 방의 넓이
    private static int removeWallMaxRoom = 0; // 하나의 벽을 제거했을 때의 가장 넓은 방의 크기

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[M][N];
        visit = new boolean[M][N];
        walls = new int[M][N][2];

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

        int roomCnt = 0; // 방 개수
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visit[i][j]) {
                    bfs(i, j, roomCnt);
                    roomCnt++;
                }
            }
        }

        getMaxAreaRoom();

        bw.write(roomCnt + "\n" + maxRoom + "\n" + removeWallMaxRoom);
        bw.flush();
    }

    private static void bfs(int r, int c, int id) {
        Queue<Node> queue = new LinkedList<>();
        visit[r][c] = true;
        queue.offer(new Node(r, c));

        ArrayList<Node> list = new ArrayList<>();
        int area = 0;
        while (!queue.isEmpty()) {
            Node n = queue.poll();
            area++;
            list.add(new Node(n.r, n.c));
            for (int i = 0; i < 4; i++) {
                // 벽이 없는 경우
                if ((map[n.r][n.c] & (1 << i)) == 0) {
                    int nextR = n.r + moveR[i];
                    int nextC = n.c + moveC[i];
                    if (nextR < 0 || nextC < 0 || nextR >= M || nextC >= N) continue;
                    if (visit[nextR][nextC]) continue;
                    visit[nextR][nextC] = true;
                    queue.offer(new Node(nextR, nextC));
                }
            }
        }
        maxRoom = Math.max(maxRoom, area);

        for (Node n: list) {
            walls[n.r][n.c][0] = id;
            walls[n.r][n.c][1] = area;
        }
    }

    private static void getMaxAreaRoom() {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < 4; k++) {
                    int r = i + moveR[k];
                    int c = j + moveC[k];
                    if (r < 0 || c < 0 || r >= M || c >= N) continue;
                    if (walls[i][j][0] != walls[r][c][0]) {
                        removeWallMaxRoom = Math.max(removeWallMaxRoom, walls[i][j][1]+walls[r][c][1]);
                    }
                }
            }
        }
    }

    private static class Node {
        int r, c;
        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}