2234번(성곽)

첫 시도

• 단순 bfs로 구현 가능할 것으로 생각했다
• 문제 1. 벽 방향 정보를 구하기 위해서는 입력받은 값을 이진수로 변환해서 계산해주어야 한다.
• 문제 2. 단순 bfs로는 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구할 수 없다.
• 구현 실패

해결

• 해결 1. 입력받은 값을 이진수로 변환해서 계산해도 되지만 더 쉬운 방법인 비트마스킹을 사용한다 -> 4방탐색할때 입력받은 값과 1,2,4,8을 &연산 해주면 된다. 만약 연산값이 0이 나온다면 해당 방향의 벽이 없다는 뜻
• 해결 2. bfs로 순환하면서 방마다 방을 구분할 수 있는 숫자를 넣는다 -> 4방탐색 시 처음방문하는 곳이 아니고 같은 방이 아니라면 list에 추가, 즉 list 안에는 이웃한 방의 번호가 저장됨 -> bfs후 list를 돌면서 Math.max(현재 방의 크기 + 이웃한 방의 크기, 지금까지 구한 최대 방 크기)
• 핵심 로직은 bfs + list로 이웃한 방 크기 확인하기이므로 시간 복잡도는 O(4NM+4NM)정도로 예상

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    // input
    static int N, M,room =0, maxNum = 0;
    static int[][] map, wall;
    // bfs
    static Deque<int[]> deque;
    static int[] dx = { 0, -1, 0, 1 };
    static int[] dy = { -1, 0, 1, 0 };
    static int[] dir = { 1, 2, 4, 8 };
    static ArrayList<Integer> space =  new ArrayList();
    static HashMap<Integer, Set<Integer>> side = new HashMap<>();

    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        wall = new int[N][M];
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                wall[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        int num = 1;
        deque = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    bfs(i, j, num++);
                    room++;
                }
            }
        }

        System.out.println(room);
        System.out.println(maxNum);
        int sum = 0;
        for (int i = 1; i <= room; i++) {
            if (side.get(i) != null) {
                for (int j : side.get(i)) {
                    sum = Math.max(space.get(i-1) + space.get(j-1), sum);
                }
            }
        }
        System.out.println(sum);
    }

    private static void bfs(int x, int y, int num) {
        int nx, ny, cnt =0;
        int[] pos = new int[2];
        deque.add(new int[] { x, y });
        map[x][y] = num;
        Set<Integer> set = new HashSet<>();
        while (!deque.isEmpty()) {
            pos = deque.poll();
            x = pos[0];
            y = pos[1];
            cnt++;
            for (int i = 0; i < 4; i++) {
                nx = x + dx[i];
                ny = y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M)
                    continue;
                if (map[nx][ny] != 0 && map[nx][ny] != num) {
                    set.add(map[nx][ny]);
                    continue;
                }
                if ((wall[x][y] & dir[i]) == 0
                        && map[nx][ny] == 0) {
                    deque.add(new int[] { nx, ny });
                    map[nx][ny] = num;
                    continue;
                }

            }
        }
        side.put(num, set);
        space.add(cnt);
        maxNum = Math.max(maxNum, cnt);
    }
}

참고

• https://sohee-dev.tistory.com/50