<BOJ>1992번: 쿼드트리

문제

1992번: 쿼드트리

접근

• 1780번: 종이의 개수, 2630번: 색종이 만들기 문제와 비슷하다.
• 분할 정복의 아이디어대로 범위를 쪼개가며 판단해야 한다.
• if문을 두어 범위 내의 모든 원소가 1 또는 0으로 통일되는지를 기준으로 쿼드트리를 나누자.
• 재귀를 들어가는 부분은 (, 나오는 부분은 )를 넣어줘야 한다.
• 다음 그림과 같이 좌상단, 우상단, 좌하단, 우하단 4개의 범위로 나눠 분할 정복을 수행한다. newSize = size / 2 와 같은 꼴로 반복 될 것이다.
  

내 코드

import java.io.*;

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static int[][] grid;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                grid[i][j] = str.charAt(j) - '0';
            }
        }
        solution(0, 0, n);
        System.out.println(sb);
    }

    public static void solution(int x, int y, int size) {
        if (check(x, y, size)) {
            sb.append(grid[x][y]);
            return;
        }
        int newSize = size / 2;

        sb.append('(');
        solution(x, y, newSize);
        solution(x, y + newSize, newSize);
        solution(x + newSize, y, newSize);
        solution(x + newSize, y + newSize, newSize);
        sb.append(')');
    }

    public static boolean check(int x, int y, int size) {
        int value = grid[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (value != grid[i][j]) return false;
            }
        }
        return true;
    }
}

grid[x][y]는 x, y의 좌표라 생각하여 check()는 이 좌표를 출발점으로 size만큼 2중 for문으로 완전탐색을 하며 색깔이 모두 같은지를 판단한다.

solution()으로 재귀를 하는 부분은 앞서 언급했던 4방향에 대한 재귀를 수행하는 부분이다. 이런 패턴을 잘 기억해두면 재귀/분할정복에 대해 어느정도 감이 잡혀갈 것이라 생각한다.