[JAVA] 2234 - 성곽 💛3 : DFS 조건 자체를 비트마스킹으로 주는 문제 with 아이디어가 필요한 Connected Component 풀이

들어가며

https://www.acmicpc.net/problem/2234

 

DFS 문제를 많이 풀어봤다면 딱 읽자마자 Connencted Component, 즉 DFS를 돌며 방의 갯수를 counting하는 문제구나라는 것을 빠르게 알 수 있을 것이다. 다만 이 문제는 3번째 출력 값인 "하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기"를 구하는 것이 아이디어가 도저히 생각이 안났다. 결론은 너무 괜찮은 아이디어가 추가되어야 풀리는 문제였기에 그 고민의 과정을 담아본다.

본문으로

특히 이 문제는 입력부터가 매우 흥미로웠다. 보통 좌표의 값을 제공해서 그 값을 활용하여 다음 좌표로 이동할지 말지를 정하는데, 벽을 표현하기 위해 이진수 값을 주어지는 게 큰 특징이었다. 각 방향에 벽이 있다면 서쪽(0001), 북쪽(0010), 동쪽(0100), 남쪽(1000)이었다. 방은 모든 벽으로 둘러쌓이는 경우는 문제에서 없다고 주어졌으므로 주어지는 벽의 정보의 범위는 0~15임을 알 수 있다.

 

아래는 그 벽을 확인하는 로직으로 비트연산자를 활용해서 정답을 아래와 같이 제출했다.

public class Main {

    static int Y, X, rooms, maxRoom, afterMaxRoom;
    static int[][] maps, visited;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static boolean isWallBroken;
    static List<Node> list;

    static class Node {
        int y;
        int x;

        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static int go(Node node) {
        visited[node.y][node.x] = 1;
        int cnt = 1;
        for (int i = 0; i < 4; i++) {
            int ny = node.y + dy[i];
            int nx = node.x + dx[i];
            if (ny < 0 || nx < 0 || ny >= Y || nx >= X || visited[ny][nx] != 0 || isWall(maps[node.y][node.x], dy[i],
                    dx[i])) {
                continue;
            }

            cnt += go(new Node(ny, nx));
        }
        return cnt;
    }

    static int goWall(Node node, boolean canBreak) {
        if (isWallBroken) {
            list.add(node);
        }

        visited[node.y][node.x] = 1;
        int cnt = 1;

        for (int i = 0; i < 4; i++) {
            int ny = node.y + dy[i];
            int nx = node.x + dx[i];

            if (ny < 0 || nx < 0 || ny >= Y || nx >= X || visited[ny][nx] != 0) {
                continue;
            }

            if (isWall(maps[node.y][node.x], dy[i], dx[i])) {

                if (canBreak) {
                    isWallBroken = true;
                    cnt += goWall(new Node(ny, nx), false);
                }

            } else {
                cnt += goWall(new Node(ny, nx), canBreak);
            }
        }

        return cnt;
    }


    static boolean isWall(int wall, int dy, int dx) {
        if (dx == -1 && ((wall & (1 << 0)) != 0)) { // 서쪽으로 가려는데 벽이면 못감
            return true;
        }
        if (dy == -1 && ((wall & (1 << 1)) != 0)) { // 북쪽으로 가려는데 벽이면 못감
            return true;
        }
        if (dx == 1 && ((wall & (1 << 2)) != 0)) { // 동쪽으로 가려는데 벽이면 못감
            return true;
        }
        if (dy == 1 && ((wall & (1 << 3)) != 0)) { // 남쪽으로 가려는데 벽이면 못감
            return true;
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        maps = new int[Y][X];
        visited = new int[Y][X];
        list = new ArrayList<>();

        rooms = 0;
        maxRoom = 0;
        afterMaxRoom = 0;

        for (int i = 0; i < Y; i++) {
            StringTokenizer walls = new StringTokenizer(bf.readLine());
            for (int j = 0; j < X; j++) {
                maps[i][j] = Integer.parseInt(walls.nextToken());
            }
        }

        for (int i = 0; i < Y; i++) {
            for (int j = 0; j < X; j++) {
                if (visited[i][j] == 0) {
                    maxRoom = Math.max(go(new Node(i, j)), maxRoom);
                    rooms++;
                }
            }
        }

        visited = new int[Y][X];
        for (int i = 0; i < Y; i++) {
            for (int j = 0; j < X; j++) {
                if (visited[i][j] == 0) {
                    isWallBroken = false;
                    for (Node node : list) {
                        visited[node.y][node.x] = 0;
                    }
                    list = new ArrayList<>();
                    afterMaxRoom = Math.max(goWall(new Node(i, j), true), afterMaxRoom);
                }
            }
        }

        System.out.println(rooms);
        System.out.println(maxRoom);
        System.out.println(afterMaxRoom);


    }
}

문제의 출력값이 방의 갯수와 가장 큰 방의 크기는 잘 출력하는데, 여전히 "하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기"를 구하고 있지 못한다. boolean인 isWallBroken 값으로 분기를 나눠서 원상복귀하기 위한 list도 선언해서 별짓거리 다해봤는데.. 틀렸다. 사실 아마 성공해도 시간복잡도에서 터졌을 것이다.

그나마 잘 구현했다고 생각하는 것은 아래의 로직이다. dy, dx의 값을 인자로 받아 비트 연산자를 활용해 문제에서 제공해준 조건대로 해당 비트가 켜져있으면 벽인 것으로 판정되게끔 구현했다.

    static boolean isWall(int wall, int dy, int dx) {
        if (dx == -1 && ((wall & (1 << 0)) != 0)) { // 서쪽으로 가려는데 벽이면 못감
            return true;
        }
        if (dy == -1 && ((wall & (1 << 1)) != 0)) { // 북쪽으로 가려는데 벽이면 못감
            return true;
        }
        if (dx == 1 && ((wall & (1 << 2)) != 0)) { // 동쪽으로 가려는데 벽이면 못감
            return true;
        }
        if (dy == 1 && ((wall & (1 << 3)) != 0)) { // 남쪽으로 가려는데 벽이면 못감
            return true;
        }

        return false;
    }

---

그렇다면 다음이 문제였다.

💡 벽을 허물며 재귀적으로 탐색하고 원상복귀 하는식으로 진행하면 무조건 시간복잡도가 터질텐데, 어떻게 벽을 허무는 케이스를 모두 고려할까?

---

다른 분들의 코드를 참고하며... 찾아낸 너무 좋은 아이디어는 다음과 같다.

💡 한번 재귀적으로 쭉 탐색한 방을 구분할 수 있다면, 붙어있는 부분만 연결시켜준다음 최대값을 찾으면 되지 않을까?

여태까지 visited는 방문처리만을 위한 0 ,1 저장뿐이었는데, 방문한 방을 처리하기위해 단순한 방문 여부만 아니라 방의 번호, 즉 n번째 dfs인지를 visited에 저장하면 connected Component를 구분할 수 있다. 아래는 최종 제출 코드이다.

public class Main {

    static int Y, X, rooms, maxRoom, afterMaxRoom;
    static int[][] maps, visited;
    static int[] dy = {0, -1, 0, 1};
    static int[] dx = {-1, 0, 1, 0};
    static int[] roomCosts; // Connected Component 저장값

    static class Node {
        int y;
        int x;

        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static int go(Node node, int roomNum) {
        visited[node.y][node.x] = roomNum;
        int cnt = 1;
        for (int i = 0; i < 4; i++) {
            if ((maps[node.y][node.x] & (1 << i)) == 0) {
                int ny = node.y + dy[i];
                int nx = node.x + dx[i];
                if (ny < 0 || nx < 0 || ny >= Y || nx >= X || visited[ny][nx] != 0) {
                    continue;
                }

                cnt += go(new Node(ny, nx), roomNum);
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        maps = new int[Y][X];
        visited = new int[Y][X];

        rooms = 0;
        maxRoom = 0;
        afterMaxRoom = 0;

        for (int i = 0; i < Y; i++) {
            StringTokenizer walls = new StringTokenizer(bf.readLine());
            for (int j = 0; j < X; j++) {
                maps[i][j] = Integer.parseInt(walls.nextToken());
            }
        }

        roomCosts = new int[Y * X + 4];
        int roomNum = 1;
        for (int i = 0; i < Y; i++) {
            for (int j = 0; j < X; j++) {
                if (visited[i][j] == 0) {
                    int roomSize = go(new Node(i, j), roomNum);
                    maxRoom = Math.max(roomSize, maxRoom);
                    roomCosts[roomNum] = roomSize;
                    rooms++;
                    roomNum++;
                }
            }
        }

        for (int i = 0; i < Y; i++) {
            for (int j = 0; j < X; j++) {
                if (i + 1 < Y) {
                    int up = visited[i][j];
                    int down = visited[i + 1][j];

                    if (up != down) {
                        afterMaxRoom = Math.max(afterMaxRoom, roomCosts[up] + roomCosts[down]);
                    }
                }
                if (j + 1 < X) {
                    int left = visited[i][j];
                    int right = visited[i][j + 1];

                    if (left != right) {
                        afterMaxRoom = Math.max(afterMaxRoom, roomCosts[left] + roomCosts[right]);
                    }
                }
            }
        }

        System.out.println(rooms);
        System.out.println(maxRoom);
        System.out.println(afterMaxRoom);


    }
}

 

그리고 코드를 보면 아까 위에서 잘 썻다고 생각했다던 isWall()메서드가 사라진 것을 볼 수 있는데, 아래와 같이 바뀌었다. 생각해보면 이미 maps[y][x] 안에 벽에 대한 정보가 담겨있기에 dy, dx의 이동방향을 문제에서 제공한 증가방향(서,북,동,남)으로 바꾼다면 아래와 같이 한줄로 정리할 수 있다.

if ((maps[node.y][node.x] & (1 << i)) == 0) {
                int ny = node.y + dy[i];
                int nx = node.x + dx[i];
                if (ny < 0 || nx < 0 || ny >= Y || nx >= X || visited[ny][nx] != 0) {
                    continue;
                }

                cnt += go(new Node(ny, nx), roomNum);
            }

---

마무리하며

dfs, Connected Component 문제는 어느정도 익숙해졌다고 생각했는데, 이렇게 다른 개념 하나만 추가되어도 쉽게 풀지 못한다... dfs로직을 거의 외우다시피 해서 그것을 활용하는 연습이 부족하다고 생각한다!! 앞으로도 정말 많이 풀어야겠다.

 

그리고 이 문제에서의 큰 가르침은, visited 방문배열에 방문여부 뿐만 아니라 다양한 값을 저장해서 방문한 곳의 상태를 여러가지 조건으로 저장할 수 있다는 점이었다!! 꼭 기억해서 방문배열을 여러가지 방법으로 써먹자!