[백준]#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

풀이

이 문제는 기본적으로 DFS 알고리즘을 이용해서 풀었다. DFS 알고리즘을 이용해서 방의 개수와, 인근 방의 번호를 구해서 인접 방의 벽을 부쉈을 때 가장 큰 값을 구하는 방식을 이용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;

public class Main {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean[][] visited;
    static int N;
    static int M;
    static String[][] map;
    static int size;
    static ArrayList<Integer> list = new ArrayList<>();
    static int max = Integer.MIN_VALUE;
    static int[][] num_map;
    static int nRoom = 0;
    static HashSet<Integer>[] near;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[1]);
        M = Integer.parseInt(input[0]);
        map = new String[N][M];
        visited = new boolean[N][M];
        num_map = new int[N][M];

        StringBuffer deciFormat = new StringBuffer();
        for (int inx = 0; inx < 4; inx++)
            deciFormat.append("0");
        DecimalFormat df = new DecimalFormat(deciFormat.toString());

        for(int i=0; i<N; i++) {
            input = br.readLine().split(" ");
            for(int j=0; j<M; j++)
                map[i][j] = df.format(Integer.parseInt(Integer.toBinaryString(Integer.parseInt(input[j]))));
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(!visited[i][j]) {
                    nRoom++;
                    size = 1;
                    visited[i][j] = true;
                    num_map[i][j] = nRoom-1;
                    countRoom(i, j);
                    list.add(size);
                    max = Math.max(max, size);
                }
            }
        }

        near = new HashSet[nRoom];
        for(int i=0; i<nRoom; i++)
            near[i] = new HashSet<>();
        visited = new boolean[N][M];
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(!visited[i][j]) {
                    visited[i][j] = true;
                    nearRoom(i, j);
                }
            }
        }

        int res = Integer.MIN_VALUE;
        for(int i=0; i<nRoom; i++) {
            Iterator it=near[i].iterator();
            while(it.hasNext()){
                res = Math.max(list.get(i)+list.get((int)it.next()), res);
            }
        }

        System.out.println(nRoom+"\n"+max+"\n"+res);
    }

    public static void countRoom(int x, int y) {
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(nx<0 || nx>=N || ny<0 || ny>=M || map[x][y].charAt(i)=='1' || visited[nx][ny]) continue;

            visited[nx][ny] = true;
            num_map[nx][ny] = nRoom-1;
            size++;
            countRoom(nx, ny);
        }
    }

    public static void nearRoom(int x, int y) {
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny]) continue;

            if(num_map[x][y]==num_map[nx][ny]) {
                visited[nx][ny] = true;
                nearRoom(nx, ny);
            }

            else
                near[num_map[x][y]].add(num_map[nx][ny]);
        }
    }
}