[백준] 1992번: 쿼드트리

문제

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

1992번: 쿼드트리

 

풀이

재귀를 사용해 풀었습니다.
현재 구역의 색상이 모두 같으면 해당 색상을 출력합니다.
만약 다르다면 4개의 구역으로 분할하고 재확인해 괄호와 함께 출력합니다.
재귀를 이용하여 색상이 다르면 계속해서 분할하여 확인하게 됩니다.

 

코드

자바

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

public class Main {
    public static char[][] image;

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

    public static void QuadTree(int x, int y, int n) {
        if (check(x, y, n)) {
            System.out.print(image[x][y]);
        } else {
            System.out.print('(');
            n /= 2;
            QuadTree(x, y, n);
            QuadTree(x, y + n, n);
            QuadTree(x + n, y, n);
            QuadTree(x + n, y + n, n);
            System.out.print(')');
        }
    }

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

        int N = Integer.parseInt(br.readLine());

        image = new char[N][N];
        for (int i = 0; i < N; i++) {
            image[i] = br.readLine().toCharArray();
        }

        QuadTree(0, 0, N);
    }
}

파이썬

import sys

input = sys.stdin.readline


def check(x, y, n):
    for i in range(x, x + n):
        for j in range(y, y + n):
            if image[i][j] != image[x][y]:
                return False
    return True


def QuadTree(x, y, n):
    if check(x, y, n):
        print(image[x][y], end="")
    else:
        print("(", end="")
        n //= 2
        QuadTree(x, y, n)
        QuadTree(x, y + n, n)
        QuadTree(x + n, y, n)
        QuadTree(x + n, y + n, n)
        print(")", end="")


N = int(input())
image = [list(input().rstrip()) for _ in range(N)]

QuadTree(0, 0, N)