[백준] 2234번 성곽 - Java

문제 링크

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의 답을 출력한다.

알고리즘: BFS, 비트마스킹

풀이

문제에 1번 이 성에 있는 방의 개수와 2번 가장 넓은 방의 넓이는 간단하게 BFS로 구하면 된다.
3번은 하나의 벽을 제거해서 가장 넓은 방의 크기를 구하는 것인데, 인접한 방끼리 넓이를 더해서 그중 가장 큰 값을 구하면 된다.

솔루션은 간단하나 진행 방향을 찾는 방법이 조금 까다롭다. 간단하게 구현하기 위해서 비트마스킹을 사용하면 된다.
1, 2, 4, 8의 이진수 값은 0001, 0010, 0100, 1000이고, 입력으로 주어진 벽에 대한 정보와 &(and)연산을 했을 때 0이 아닌 1, 2, 4, 8이 나오면 그 방향은 벽이 있기 때문에 진행할 수 없는 방향이다. 반대로 0이면 일치하지 않다는 의미이기 때문에 그 방향은 진행할 수 있는 방향이다.
이런 식으로 비트마스킹을 이용해서 간단하게 진행 방향을 구할 수 있다.

소스 코드

import java.io.*;
import java.util.*;

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

public class Main {
    static final int dx[] = {-1, 0, 1 ,0};
    static final int dy[] = {0, -1, 0, 1};
    static final int dir[] = {1, 2, 4, 8};
    static int N,M;
    static int castle[][];
    static int room_area[][];
    static boolean visited[][];
    static int room_number = 0;
    static int max_size = -1;
    static int max_size2 = -1;
    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());
        castle = new int[M][N];
        room_area = new int[M][N];
        visited = new boolean[M][N];
        for(int i=0; i<M; i++) {
            StringTokenizer n_st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                castle[i][j] = Integer.parseInt(n_st.nextToken());
            }
        }
        //탐색
        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                if(!visited[i][j]) {
                    room_number += 1;
                    BFS(new Point(j, i));
                }
            }
        }
        //벽 제거했을 때 가장 넓은 방 크기
        for(int i=0; i<M; i++) {
            for(int j=0; j<N; j++) {
                for(int k=0; k<4; k++) {
                    int nx = j + dx[k];
                    int ny = i + dy[k];
                    if((nx>=0 && nx<=N-1) && (ny>=0 && ny<=M-1)) {
                        if(castle[i][j] != castle[ny][nx]) {
                            //방 번호가 다르면
                            max_size2 = Math.max(max_size2, room_area[i][j] + room_area[ny][nx]);
                        }
                    }
                }
            }
        }
        System.out.printf("%d\n%d\n%d", room_number, max_size, max_size2);
    }
    static void BFS(Point start) {
        Queue<Point> que = new LinkedList<>();
        ArrayList<Point> vis_list = new ArrayList<>();
        que.add(start);
        vis_list.add(start);
        visited[start.y][start.x] = true;
        int cout = 1;
        while(que.size()!=0) {
            Point n = que.poll();
            for(int i=0; i<4; i++) {
                if((castle[n.y][n.x] & dir[i])==0) {
                    int nx = n.x + dx[i];
                    int ny = n.y + dy[i];
                    if(!visited[ny][nx]) {
                        Point next_n = new Point(nx, ny);
                        que.add(next_n);
                        vis_list.add(next_n);
                        visited[ny][nx] = true;
                        cout += 1;
                    }
                }
            }
        }
        max_size = Math.max(max_size, cout);
        for(int i=0; i<vis_list.size(); i++) {
            castle[vis_list.get(i).y][vis_list.get(i).x] = room_number;
            room_area[vis_list.get(i).y][vis_list.get(i).x] = cout;
        }
    }
}