[알고리즘] 백준 > #1992. 쿼드트리

문제링크

백준 #1992. 쿼드트리

풀이방법

계속 주어진 범위에 다른 값을 가진게 있으면 4등분하면 되는 문제다. 이렇게 작은 문제로 나눠 해결하는 방법을 분할정복이라고 한다! 주어진 범위 내 값들이 같은지 다른지를 쉽게 판단하기 위해 값들을 boolean 타입으로 저장했다. 그리고 nor 연산을 진행해 이를 판단했다. 끝!

코드

class Solution1992 {

    int size;
    boolean[][] map;

    final int[] dy = {0, 0, 1, 1};
    final int[] dx = {0, 1, 0, 1};

    Solution1992(int size, boolean[][] map) {
        this.size = size;
        this.map = map;
    }

    String getQuadTree() {
        return getQuadTree(0, 0, size);
    }

    String getQuadTree(int y, int x, int size) {
        String quadTree = "";

        boolean isAllSame = true;
        boolean check = map[y][x];
        for (int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                if (check^map[i][j]) {
                    isAllSame = false;
                    break;
                }
            }
            if (!isAllSame) break;
        }

        if (isAllSame) quadTree += (map[y][x] ? '1' : '0');
        else {
            quadTree += "(";
            int nextSize = size / 2;
            for (int i = 0; i < 4; i++) quadTree += getQuadTree(y + nextSize * dy[i], x + nextSize * dx[i], nextSize);
            quadTree += ")";
        }

        return quadTree;
    }
}