boj 1992 쿼드트리

www.acmicpc.net/problem/1992

1992번: 쿼드트리

한 구간에 0과 1로만 이루어져있으면 그 숫자를 출력, 아니면 괄호를 만들고 구간을 1/4로 나눠서 재귀를 돌려야하는 문제입니다.

 

우선 맨 처음 x, y에 들어있는 값을 저장해놓고, 이 값과 구간에 있는 모든 값과 비교해서

모두 같으면 ch 출력

다른게 있으면 인덱스를 이용하여 1/4로 나누었습니다.

여기서 재귀를 4번 돌리기 전에 "("를 출력해주고, 4번의 재귀가 끝나면 ")"를 출력해야합니다.

 

만약 size가 1이면 확인할 필요가 없기때문에 list[x][y]를 바로 출력하고 리턴합니다.

 

 

import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static char list[][];
    static int N;
 
    static void func(int size, int x, int y) {
        if (size == 1) {
            sb.append(list[x][y]);
            return;
        }
 
        boolean chk = false;
        char ch = list[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (ch != list[i][j]) {
                    chk = true;
                    break;
                }
            }
            if (chk)
                break;
        }
 
        if (chk) {
            sb.append("(");
            func(size / 2, x, y);
            func(size / 2, x, (y + y + size) / 2);
            func(size / 2, (x + x + size) / 2, y);
            func(size / 2, (x + x + size) / 2, (y + y + size) / 2);
            sb.append(")");
        } else {
            sb.append(ch);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new char[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(N, 0, 0);
        System.out.println(sb.toString());
    }
}