[Gold III] 성곽 - 2234 (Java)

문제 요약

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

이 성에 있는 방의 개수
가장 넓은 방의 넓이
하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

---

문제 분석

비트마스킹을 위해 dr, dc, wall의 배열을 생성해서 특정 방향에 맞는 벽의 숫자를 저장한다.
전체 bfs탐색하며 방의 개수와 넓은방의 넓이를 우선 구해준다.
다시 전체 bfs를 돌며 현재 위치와 다음 위차의 영역이 다르다면 두 영역의 넓이를 더해 정답을 갱신한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] map, visited;
    static int[] result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        /*
            0. 이 성에 있는 방의 개수
            1. 가장 넓은 방의 넓이
            2. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
         */
        result = new int[3];
        map = new int[M][N];
        visited = new int[M][N];
        for(int r = 0; r < M; r++){
            st = new StringTokenizer(br.readLine());
            for(int c = 0; c < N; c++){
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }
//        for(int[] a : map){
//            System.out.println(Arrays.toString(a));
//        }
//        System.out.println("-----------------------------------");
        // 왼쪽벽이 있으면 1을, 위쪽벽이 있으면 2를,
        // 오른쪽 벽이 있으면 4를, 아래쪽 벽이 있으면 8
        int number = 0;
        List<Integer> areaList = new ArrayList<>();
        for(int r = 0; r < M; r++){
            for(int c = 0; c < N; c++){
                if(visited[r][c] == 0){
                    areaList.add(bfs(r, c, ++number));
                }
            }
        }
        // 0. 이 성에 있는 방의 개수
        result[0] = number;
//        for(int[] a : visited){
//            System.out.println(Arrays.toString(a));
//        }
        // 2. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
        // 이제 이걸 어떻게 구해야할지 생각해보자.
        // 전체를 순차탐색하면서 해당하는 위치에서 어떤 벽을 없앨 수 있는지 확인하고,
        // 벽을 지운 방향에 다른 영역이 존재하면, 그 영역의 값과 현재 영역의 값을 더해 최고값 갱신
        for(int r = 0; r < M; r++){
            for(int c = 0; c < N; c++){
                for(int d = 0; d < 4; d++){
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if(nr < 0 || nc < 0 || nr >= visited.length || nc >= visited[0].length){
                        continue;
                    }
                    if(visited[r][c] != visited[nr][nc]){
                        result[2] = Math.max(result[2], areaList.get(visited[r][c]-1) + areaList.get(visited[nr][nc]-1));
                    }
                }
            }
        }
//        System.out.println("-----------------------------------");
//        System.out.println(Arrays.toString(result));
        for(int i : result){
            System.out.println(i);
        }
    }

    static int[] dr = {-1, 0, 1, 0};  // 북, 동, 남, 서 순서
    static int[] dc = {0, 1, 0, -1};  // 북, 동, 남, 서 순서
    static int[] heading = {2, 4, 8, 1};  // 북, 동, 남, 서 순서


    private static int bfs(int R, int C, int number) {
        int area = 1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{R,C});
        visited[R][C] = number;
        while(!q.isEmpty()){
            int[] curr = q.poll();
            int r = curr[0];
            int c = curr[1];
            for(int d = 0; d < 4; d++){
                int nr = r + dr[d];
                int nc = c + dc[d];
                if(nr < 0 || nc < 0 || nr >= visited.length || nc >= visited[0].length){
                    continue;
                }
                // 이쪽 방향이 뚫린 방향인지 확인.
                if((map[r][c] & heading[d]) != 0){
                    continue;
                }
                if(visited[nr][nc] != 0){
                    continue;
                }
                visited[nr][nc] = number;
                q.add(new int[]{nr, nc});
                area++;
            }
        }
        // 1. 가장 넓은 방의 넓이
        result[1] = Math.max(result[1], area);
        return area;
    }
}

---

정리

새로 배운 내용

비트마스킹 은근 어렵다.

개선할 점

없음

더 찾아볼만한 사항

비트마스킹

---