[BAEKJOON] 2234 성곽 (Java)

[ 문제 ]

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

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, 북2, 동4, 남8 일때, 맵 한곳의 자리를 Value라고 한다면

1→2→4→8 은 비트마스크로 1<<0, 1<<1, 1<<2, 1<<3 으로 표현가능 하다

 

Value가 15일때 2진수로 1111이고, 이를 4값과 비교하려면

& 연산을 통해 1,2,4,8의 값을 지니고있는지 판별할 수 있다.

위 4방향은 비트마스크로 표현할때 K: 0~3, 1<<K 라고 표현할 수 있기에

맵에서 벽이 둘러싸여있는 방향은 ((1<<K) & Value)로 나타낼 수 있따.

 

이만 잘 받아주면, 나머지는 첫  bfs를 통해 알아낼 수 있다.

0) 비트마스크를 사용하여 성벽위치 알아내기

1) 성안에 방이 몇개있는지 찾기

2) 성안의 방들은 각각 몇칸을 차지하고있는지 찾기

3) 벽을하나 허물었을때, 최대칸수는 몇칸인지

여기서 주의할점이 3번이다.

각 배열에서 4방향을 판별할때, 방향으로간 배열에서 또한번 그벽을 검사하기때문에 메모리초과를 유발한다.

 

그래서 생각할 수 있는게,

1) 성안에 방이 몇개있는지 찾으면서, 각 방에는 번호를 부여해주기

2) 성안에 방들은 각각 몇칸을 차지하고있는지 1)과 동시에 계산하면서 이후 해당 값을지닌 배열을 만들기

3) 벽을 허물었을때, 한번더 탐색하는게아닌, 1)에서 부여된 번호를 비교하여

같다면 허물어도 그방의 값은 똑같고, 다르다면 두 번호의 방들이 가진 값을 합하여 반환하면된다.

[ Java ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class xy_2234 {
    int y;
    int x;
    xy_2234(int y, int x){
        this.y=y;
        this.x=x;
    }
}
public class _2234_성곽 {
    static final int MAX = 51;
    static int W, H;
    static int ay[] = {0, -1, 0, 1};	//서 북 동 남
    static int ax[] = {-1, 0, 1, 0};
    static boolean map[][][] = new boolean[MAX][MAX][4];
    static boolean visit[][] = new boolean[MAX][MAX];
    static int zone[] = new int[MAX*MAX];
    static int castle[][] = new int[MAX][MAX]; 

    static Queue<xy_2234>q=new LinkedList<xy_2234>();
    static StringBuilder sb = new StringBuilder();
    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        for(int i=0;i<H;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<W;j++) {
                int value = Integer.parseInt(st.nextToken());
                for(int k=0;k<4;k++) {
                    if (((1<<k) & value) != 0) 
                        map[i][j][k] = true;
                }
            }
        }
        System.out.println(make());
        System.out.println(solve());
        System.out.println(break_wall());
    }
    static int make() {
        for(boolean item[] : visit)
            Arrays.fill(item, false);
		
        int room=0;
        for(int i=0;i<H;i++)
            for(int j=0;j<W;j++) {
                if (!visit[i][j]) {
                    int cnt=0;
                    q.add(new xy_2234(i, j));
                    visit[i][j] = true;
                    castle[i][j] = room;
                    while(!q.isEmpty()) {
                        xy_2234 item = q.poll();
                        cnt++;
                        for(int k=0;k<4;k++) {
							int ny = item.y+ay[k];
							int nx = item.x+ax[k];
							if (!range(ny, nx) && !visit[ny][nx] && !map[item.y][item.x][k]) {
                                visit[ny][nx] = true;
                                castle[ny][nx] = room;
                                q.add(new xy_2234(ny, nx));
                            }
                        }
                    }
                    zone[room++]=cnt;
                }
            }
        return room;
    }
    static int solve() {
        int value = 0;
        for(int item : zone)
            value = value > item ? value : item;
        return value;
    }
    static int break_wall() {
        int result = 0;
        for(int i=0;i<H;i++)
            for(int j=0;j<W;j++) {
                for(int k=0;k<4;k++) {
                    int ny = i+ay[k];
                    int nx = j+ax[k];
                    if (!range(ny, nx) && map[i][j][k]) {
                        if (castle[i][j] != castle[ny][nx]) {
                            int value = zone[castle[i][j]]+zone[castle[ny][nx]];
                            result = result > value ? result : value;
                        }
                    }
                }
            }
        return result;
    }
    static boolean range(int y, int x) {
        return y<0||x<0||y>H-1||x>W-1;
    }
    public static void main(String[] args) throws IOException {
        init();
    }
}