2234번 : 성곽 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공 (52분 27초)

아이디어

일단 구해야 하는 것이 총 3개이다.
이 성에 있는 방의 개수, 가장 넓은 방의 넓이, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
차례대로 구해보면
1.2. BFS로 각 방의 개수 파악 및 가장 넓은 방의 넓이 구하기 -> 우선순위큐의 size와 max값을 뽑으면
우선순위큐 하나로 2개를 구할 수 있다. 이 부분은 단순 BFS를 진행해주며 영역의 크기만 구하면 되기 때문에 간단함.

그러나 난관인 것은 3. 임의의 벽을 하나 제거했을때 가장 넓은 영역의 넓이를 구하는 것이다.
일단 두가지 방법을 생각했는데

첫번째 방법: 벽을 하나씩 제거해보고 가장 커지는 값을 구해서 마지막에 한꺼번에 출력하는 방법
너무 비효율적이라고 생각했다. 이유는 벽의 개수가 매우 많은데 그 벽을 하나씩 제거해볼때마다 그만큼의 BFS를 돌아야하기 때문

두번째 방법: 영역을 그래프처럼 생각해서 이어져있는 영역을 합치는 방법이 가장 효과적으로 보임
이걸 위해서 나는 3단계를 3개로 디테일하게 단계를 구상해 보았다.

3-1. 해당 영역의 넓이를 표시한 map하나 추가
3-2. 영역 번호가 적힌 맵에서 인접한 영역을 순회하며 연결
3-3. 영역 별로 인접한 영역 너비 합 pq에 넣기(사전에 우선순위큐 초기화 필수)

그리고 마지막에 뽑아서 출력하면 끝.

풀이코드

import java.io.*;
import java.util.*;
public class Main {
    static int N, M;
    static int [][] map, groups;
    static boolean [][] visited;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer NM = new StringTokenizer(br.readLine());
        N = Integer.parseInt(NM.nextToken());
        M = Integer.parseInt(NM.nextToken());
        map = new int[M][N];
        groups = new int[M][N];
        visited = new boolean[M][N];
        HashMap<Integer, Integer> areaMap = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int group = 1;
        // 1.2. 각 구분된 영역 구해서 최대 넓이와 개수 구하기
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(o1->(-1)*o1));
        for(int i=0; i<M; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j]){
                    int area = BFS(i, j, group);
                    pq.add(area);
                    areaMap.put(group, area);
                }
                group++;
            }
        }
        sb.append(pq.size()+"\n"+pq.poll()+"\n");
        pq.clear();
        for(int i=0; i<M; i++){
            for(int j=0; j<N; j++){
                int groupA =groups[i][j];
                for(int dir = 0; dir<4; dir++){
                    int xB = i+dx[dir];
                    int yB = j+dy[dir];
                    if(!canGo(xB, yB)){
                        continue;
                    }
                    int groupB = groups[xB][yB];
                    if(groupA==groupB) {
                        continue;
                    }
                    int sumArea = areaMap.get(groupA) + areaMap.get(groupB);
                    pq.add(sumArea);
                }
            }
        }
        sb.append(pq.poll());
        System.out.print(sb);
    }
    static int [] wallDir = {1, 2, 4, 8};//서 북 동 남
    static int [] dx = {0, -1, 0, 1};
    static int [] dy = {-1, 0, 1, 0};
    static int BFS(int i, int j, int group){
        int cnt = 0;
        groups[i][j] = group;
        ArrayDeque<int []> q = new ArrayDeque<>();
        q.add(new int []{i, j});
        visited[i][j] = true;
        while (!q.isEmpty()){
            int [] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            cnt++;
            for(int dir=0; dir<4; dir++){
                int mx = x+dx[dir];
                int my = y+dy[dir];
                if(canGo(mx, my)&&!visited[mx][my]&&(map[x][y] & wallDir[dir])==0){
                    visited[mx][my] = true;
                    groups[mx][my] = group;
                    q.add(new int []{mx, my});
                }
            }
        }
        return cnt;
    }
    static boolean canGo(int x, int y){
        return x>=0&&y>=0&&x<M&&y<N;
    }
}

(이미 연결한 영역에 대해서는 방문처리를 해서 쓸데없는 탐색을 줄였으면 더 좋은 코드였을듯 함)