[BOJ] 1992 - 쿼드트리

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1992

1992번: 쿼드트리

난이도: 실버 1

사용언어: JAVA

 

풀이

이 문제는 재귀를 이용하면 어렵지 않게 해결할 수 있습니다. 처음에 전체 영상을 모두 검사하여 만일 하나로 통일된 값이 아니면 4등분을 하여 좌측 상단 부분부터 재귀를 돌리면 됩니다. 

 

또 해당 부분이 통일된 값으로 이루어지지 않았다면, 다시 좌측 상단부터 재귀를 수행합니다. 그리고 통일된 구역이 나오면, 다음 구역을 검사하는 식으로 진행해나가면 됩니다.

 

코드를 보면서 이해하는 것이 더 좋을 것 같습니다.

 

import java.io.*;
 
class Main {
    static int N;
    static int cnt = 0;
    static char[] result = new char[1000000]; // 결과를 저장하는 배열
 
    public static void dev(int x1, int y1, int x2, int y2, char arr[][]) {
        int i, j;
        int flag = 0;
        for (i = x1; i <= x2; i++) {
            for (j = y1; j <= y2; j++) {
                if (arr[i][j] != arr[x1][y1]) { // 만일 해당 범위가 통일된 숫자로 이루어지지 않았다면
                    flag = 1; // 플래그 변수로 구분
                    break;
                }
            }
        }
        if (flag == 1) { // 만일 해당 범위가 통일된 숫자로 이루어지지 않았다면
            result[cnt++] = '('; // 우선 좌측 괄호부터 결과에 넣고
            dev(x1, y1, (x1 + x2) / 2, (y1 + y2) / 2, arr); // 좌측 상단부터 1/4 만큼 재귀 함수를 수행
            dev(x1, (y1 + y2) / 2 + 1, (x1 + x2) / 2, y2, arr); // 우측 상단
            dev((x1 + x2) / 2 + 1, y1, x2, (y1 + y2) / 2, arr); // 좌측 하단
            dev((x1 + x2) / 2 + 1, (y1 + y2) / 2 + 1, x2, y2, arr); // 우측 하단
            result[cnt++] = ')'; // 괄호 닫고
        } else {
            result[cnt++] = arr[x1][y1]; // 통일된 숫자로 이루어졌다면, 해당 숫자를 결과에 포함
        }
 
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int i, j;
        char[][] arr = new char[N][N];
        String s;
        N = Integer.parseInt(br.readLine());
 
        for (i = 0; i < N; i++) {
            s = br.readLine();
            for (j = 0; j < N; j++) {
                arr[i][j] = s.charAt(j);
            }
        }
 
        dev(0, 0, N - 1, N - 1, arr); // 재귀 시작
 
        for (i = 0; i < cnt; i++)
           bw.write(result[i]); // 결과 출력
        bw.flush();
    }
}