[백준] 2234번 : 성곽

2234번: 성곽

---

[BFS]

전체적으로 스트레스를 유발하는 문제였던 것 같다. 일단 각 정점은 상하좌우로 벽을 갖을 수 있는점, 그래서 비트마스킹을 이용해야한다는 점이...

 

각 정점은 0~15를 갖을 수 있는데,

0 : 벽이 없음

1 : 서쪽으로 벽

2 : 북쪽으로 벽

4 : 동쪽으로 벽

8 : 남쪽으로 벽

이외의 숫자는 각 벽이 갖는 값을 더한 것이다. (예: 15는 동서남북 모두 벽으로 막힌 곳)

 

#풀이 요약

1. 주어진 지도에 대해 방을 번호로 구분 (예: 1번방, 2번방, 3번방, ...) (BFS)

2. 그 때의 방의 넓이를 구하고 n개의 방 넓이 중 최대값 추출

3. 방과 방 사이의 벽을 허물어 확장했을 때 넓이가 최대값인 것 추출 (BFS_)

 

나는 2개의 BFS를 구현하였다. 먼저 첫 번째 BFS는 주어진 지도에서 전체 방의 개수를 구하고, 각 방이 갖는 넓이를 구한다. 

yy : 시작 y좌표

xx : 시작 x좌표

div : n번째 방

 

* map[y][x] & (1 << a)는 현재 위치한 정점이 해당 방향으로 벽이 있는지에 대한 식이다.

서 : a = 0

북 : a = 1

동 : a = 2

남 : a = 3

    static void BFS(int yy, int xx, int div){

        int count = 1;
        Queue<Point> Q = new LinkedList<>();

        visit[yy][xx] = true;
        room[yy][xx] = div;
        Q.add(new Point(yy, xx));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx] || (map[y][x] & (1 << a)) != 0) continue;

                count++;
                visit[ny][nx] = true;
                room[ny][nx] = div;
                Q.add(new Point(ny, nx));
            }
        }
        size[div] = count; //div번 방의 넓이
    }

R x C 지도에 대하여 위의 BFS를 수행하고 나면, 방의 개수와 각 방이 갖는 넓이를 구할 수 있다.

문제에 주어진 테스트 케이스에 대해 첫 번째 BFS를 수행하면 방의 구분이 다음과 같이 된다.

>> room[ i ][ j ]

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

 

이제 특정 방에서 벽을 하나 허물어 다른 방과 확장을 했을 때, 넓이의 최대값을 구하는 BFS를 수행하도록 한다.

   static int BFS_(int yy, int xx){
        int maxSize = 0, roomNum = room[yy][xx], roomSize = size[room[yy][xx]];

        Queue<Point> Q = new LinkedList<>();
        visit[yy][xx] = true;
        Q.add(new Point(yy, xx));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx]) continue;

                if(room[ny][nx] != roomNum){
                    maxSize = Math.max(maxSize, size[room[ny][nx]] + roomSize);
                    continue;
                }

                visit[ny][nx] = true;
                Q.add(new Point(ny, nx));
            }
        }
        return maxSize;
    }
//roomNum : 현재 방의 번호
//room[ny][nx] : 다음 정점이 위치한 방의 번호
//roomSize : 현재 방의 넓이
//size[ room[ny][nx] ] : 다음 정점이 위치한 방의 넓이

# 요약

# Code </>

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

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){
            y=yy;
            x=xx;
        }
    }
    static int r, c;
    static int[] Y = {0, -1, 0, 1}, X = {-1, 0, 1, 0}, size = new int[2501];
    static int[][] map = new int[51][51], room = new int[51][51];
    static boolean[][] visit = new boolean[51][51];

    static int BFS_(int yy, int xx){
        int maxSize = 0, roomNum = room[yy][xx], roomSize = size[room[yy][xx]];

        Queue<Point> Q = new LinkedList<>();
        visit[yy][xx] = true;
        Q.add(new Point(yy, xx));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx]) continue;

                if(room[ny][nx] != roomNum){
                    maxSize = Math.max(maxSize, size[room[ny][nx]] + roomSize);
                    continue;
                }

                visit[ny][nx] = true;
                Q.add(new Point(ny, nx));
            }
        }
        return maxSize;
    }
    static void BFS(int yy, int xx, int div){

        int count = 1;
        Queue<Point> Q = new LinkedList<>();

        visit[yy][xx] = true;
        room[yy][xx] = div;
        Q.add(new Point(yy, xx));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                if(ny < 1 || nx < 1 || ny > r || nx > c || visit[ny][nx] || (map[y][x] & (1 << a)) != 0) continue;

                count++;
                visit[ny][nx] = true;
                room[ny][nx] = div;
                Q.add(new Point(ny, nx));
            }
        }
        size[div] = count; //div번 방의 넓이
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        c = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

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

        int div = 0;
        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
                if(!visit[i][j])
                    BFS(i, j, div++);

        int max = 0;
        for(int i=0; i<=250; i++)
            if(size[i] != 0)
                max = Math.max(max, size[i]);

        boolean[] check = new boolean[div];
        int maxSize = 0;

        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++){
                int roomNum = room[i][j];

                if(!check[roomNum]){
                    visit = new boolean[51][51];
                    check[roomNum] = true;
                    maxSize = Math.max(BFS_(i, j), maxSize);
                }
            }

        System.out.println(div);
        System.out.println(max);
        System.out.println(maxSize);
    }
}