22.02.07 - [BOJ] 1992. 쿼드트리

[suhyunsim]

문제

• 쿼드트리

핵심 아이디어

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q11723;

import java.util.Scanner;

public class Main {

    public static int[][] board;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        board = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            String line = sc.next();
            for (int j = 0; j < n; j++) {
                board[i][j] = line.charAt(j) - '0';
            }
        }
        tree(0, 0, n);
        System.out.println(sb.toString());
    }

    private static void tree(int x, int y, int n) {
        if (check(x, y, n)) {
            sb.append(board[x][y]);
            return;
        }
        int after = n / 2;
        sb.append("(");
        tree(x, y, after);
        tree(x, y + after, after);
        tree(x + after, y, after);
        tree(x + after, y + after, after);
        sb.append(")");

    }

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