[Java] 백준 1992 쿼드트리

 

문제

주어진 영역 내의 숫자가 모두 같은 숫자면 해당 숫자를 출력하고,

아니라면 영역을 4등분하여 숫자가 같은지 다시 검사를 하는 문제이다.

 

 

풀이

1. 현재 영역의 숫자를 검사

2. 모두 일치하지 않는다면 현재 변의 길이(n)을 1/2하고, 현재 좌표를 기준으로 4영역으로 분할하여 함수를 재호출

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[][] map;
    static StringBuilder sb;

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

        int N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }

        recursion(0, 0, N);
        System.out.println(sb);
    }


    static void recursion(int x, int y, int len) {
        boolean isSame = true;
        int num = map[x][y];
        loop:
        for (int i = x; i < x + len; i++) {
            for (int j = y; j < y + len; j++) {
                if (num != map[i][j]) {
                    isSame = false;
                    break loop;
                }
            }
        }
        if (isSame) {
            sb.append(num);
            return;
        }

        sb.append("(");
        int nlen = len / 2;
        recursion(x, y, nlen);
        recursion(x, y + nlen, nlen);
        recursion(x + nlen, y, nlen);
        recursion(x + nlen, y + nlen, nlen);
        sb.append(")");
    }
}