BOJ - 쿼드트리

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

1992번: 쿼드트리

• 색종이 만들기 문제에서 백트렉킹이 섞인 문제이다.
• 재귀는 스텍의 성질을 가지고 있는데 이를 이용하여 괄호 치기를 하면 된다.

 

import java.io.*;
import java.util.*;


public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static StringBuilder builder = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N + 1][N + 1];

        //입력 처리
        for (int i = 0; i < N; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < chars.length; j++) {
                map[i][j] = Character.getNumericValue(chars[j]);
            }
        }

        dp(map, 0, 0, N);

        System.out.println(builder.toString());
    }

    private static void dp(int[][] map, int x, int y, int size) {
        if (size == 1) {
            builder.append(map[y][x]);
            return;
        }

        if (isFill(map, x, y, size)) {
            builder.append(map[y][x]);
            return;
        }

        //4분할
        int nextSize = size / 2;

        builder.append("(");
        dp(map, x, y, nextSize);
        dp(map, x + nextSize, y, nextSize);
        dp(map, x, y + nextSize, nextSize);
        dp(map, x + nextSize, y + nextSize, nextSize);
        builder.append(")");
    }

    /**
     * 같은 원소로 채워져 있는지 확인하는 함수
     */
    private static boolean isFill(int[][] map, int x, int y, int size) {
        int value = map[y][x];
        for (int i = y; i < y + size; i++) {
            for (int j = x; j < x + size; j++) {
                if (value != map[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }
}