[백준] no1992: 쿼드트리

문제

0과 1로 이루어진 2의 a제곱으로 된 이중배열이 있다.

배열의 숫자 중 2의 제곱수로 된 범위에 대해

1. 모두 같은 숫자면 해당 숫자를 붙인다

2. 다른 숫자면 다시 4조각으로 쪼개서 검사한다

3. 2x2배열이 됬는데도 다르면 그냥 그 안의 숫자를 모두 붙인다

4. depth당 ()로 구분한다.

 

문제 링크 : https://www.acmicpc.net/problem/1992

---

원리

재귀를 위한 가능?불가능? 판별 static 메소드를 잘 활용해야함.

 

---

풀이방법

1. 입력된 숫자를 매트릭스로 만든다. (형변환 메모리 최소화를 위해 String[][] 권장)

2. 범위는 가로 시작점, 세로 시작점, 검사하고자 하는 사이즈로 구한다.

3. 압축이 가능한지 판별한다.

4. 압축이 가능하면 범위내 첫 번째 숫자를 append 한다.

5. 압축이 불가능하다면, depth 추가 기념으로 재귀 앞뒤로 괄호를 때려넣어준다.

6. 압축불가이므로 4분할 하여 재귀를 돌려준다.

* 첫 이미지가 한큐에 안끝나면, 재귀전에 미리 사이즈를 반갈해주는게 핵심포인트

* 재귀 앞뒤로 괄호 박아주는것도 핵심 포인트

* 압축 가능하면 숫자 때리박아주고, 리턴 갈겨서 멈춰주는것도 핵심포인트

 

---

나의 코드

1. Matrix 분할 재생성형 재귀형 (실패)

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class no1992 {

    static boolean isDiff = false;

    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 N = Integer.parseInt(br.readLine());
        String[][] matrix = new String[N][N];

        for (int i = 0; i < N; i++) matrix[i] = br.readLine().split("");

        recur(matrix, N, bw);

        bw.close();
    }

    private static void recur (String[][] matrix, int N, BufferedWriter bw) throws IOException {
        isDiff = false;
        String firstNum = matrix[0][0];

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(matrix[i][j]!=firstNum) {
                    isDiff = true;
                    break;
                }
                if(isDiff) break;
            }
        }

        if(N == 2 && isDiff) bw.write("(" + matrix[0][0] + matrix[0][1] + matrix[1][0] + matrix[1][1] + ")");
        else if(isDiff) {
            String[][] first = makePaper(matrix, new String[N/2][N/2], 0,N/2-1, 0, N/2-1);
            String[][] second = makePaper(matrix, new String[N/2][N/2], N/2,N-1, 0, N/2-1);
            String[][] third = makePaper(matrix, new String[N/2][N/2], 0,N/2-1, N/2, N-1);
            String[][] quad = makePaper(matrix, new String[N/2][N/2], N/2, N-1, N/2, N-1);

            recur(first, N/2, bw);
            recur(second, N/2, bw);
            recur(third, N/2, bw);
            recur(quad, N/2, bw);
        } else bw.write(firstNum);
    }

    private static String[][] makePaper (String[][] paper, String[][] mini,
                                          int startW, int endW, int startH, int endH) {
        int miniH = 0;
        for(int i = startH; i <= endH ; i++) {
            int miniW = 0;
            for(int j = startW; j <= endW ; j++) {
                mini[miniH][miniW] = paper[i][j];
                miniW++;
            }
            miniH++;
        }
        return mini;
    }
}

2. 한 Matrix 안에서 범위를 지정하여 재귀 + 압축이 가능한지 판별 메소드(ver. BufferWriter)  [15140kB | 148ms]

public class no1992 {

    private static String[][] matrix;
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int N = Integer.parseInt(br.readLine());
        matrix = new String[N][N];

        for(int i = 0; i<N; i++) matrix[i] = br.readLine().split("");

        QuadTree( 0, 0, N);

        bw.close();
    }


    private static void QuadTree(int x, int y, int size) throws IOException {
        // 압축이 가능할 경우 하나의 색상으로 압축
        if(isPossible(x,y,size)) {
            bw.append(matrix[x][y]);
            return;
        }

        int newSize = size/2;

        bw.append("("); // 각 depth에서 여는 괄호로 시작하는 부분

        QuadTree(x, y, newSize);  // 1 사분면
        QuadTree(x, y+newSize, newSize); // 2 사분면
        QuadTree(x+newSize, y, newSize);  // 3 사분면
        QuadTree(x+newSize, y+newSize, newSize);  // 4 사분면

        bw.append(")"); // 각 depth에서 닫는 괄호로 끝나는 부분
    }

    private static boolean isPossible (int x, int y, int size) {
        String firstNum = matrix[x][y];

        // matrix의 각 부분을 나눠서 순회함. 시작점을 지정하고, 줄어든 사이즈만큼 반복하는 것
        for(int i = x; i< x+size; i++) {
            for(int j = y; j< y+size; j++) if(!firstNum.equals(matrix[i][j])) return false; // 만약 범위내에 첫번째 숫자와 다른 숫자가 있다면, 압축 불가능을 반환하고 반복중지
        }
        return true; // 범위를 다 돌았는데 문제없으면 압축 가능을 반환
    }
}

 

 

---

레퍼런스 코드

한 Matrix 안에서 범위를 지정하여 재귀 + 압축이 가능한지 판별 메소드(ver. StringBuilder)  [14820kB | 148ms]

참고 링크 : https://st-lab.tistory.com/230