BOJ_1992 : 쿼드트리

👉 문제링크

1992번: 쿼드트리

---

---

🔸 문제 분석 🔸

• n x n 크기의 영상 정보에서 0 또는 1로 압축된 결과를 출력한다.
• 정사각형이 하나의 수로만 이루어져 있으면 그 수로 압축가능하다.
  • 해당 수를 출력한다.
• 다른 수가 섞여있으면, 정사각형을 4등분해서 다시 압축한다.
  • 4등분 했을때 결과값은 () 괄호로 묶어 출력한다.
• 재귀를 이용해서 정사각형이 하나의 수로 이루어져있지 않으면 4등분 값을 다시 검사하는 방식으로 해결한다.

🔸 코드 🔸

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

public class Main {
    static int[][] arr;
    static StringBuilder sb;
    
    private static void recursion(int n, int x, int y) {
        if (check(n, x, y)) {
            sb.append(arr[x][y]);
        } else {
            sb.append("(");
            recursion(n / 2, x, y);
            recursion(n / 2, x, y + n / 2);
            recursion(n / 2, x + n / 2, y);
            recursion(n / 2, x + n / 2, y + n / 2);
            sb.append(")");
        }
    }

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

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n][n];

        for (int i = 0; i < n; i++) {
            String temp = br.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = temp.charAt(j) - '0';
            }
        }
        sb = new StringBuilder();
        recursion(n, 0, 0);
        System.out.println(sb.toString());
    }
}

🔸 코드 해석 🔸

• main 메서드에서 값을 입력받고 recursion 메서드를 호출하고, 결과를 출력한다.
• check 메서드는 정사각형이 같은 수로 이루어져있는지 확인한다.
• recursion 메서드는 정사각형의 한 변의 길이 n, 좌상단의 좌표 x,y 를 입력받는다.
  • 해당 범위의 정사각형이 같은 수로 이루어져있으면 그 수를 출력한다.
  • 다른 수가 섞여있으면 4등분해서 다시 recursion 메서드를 호출한다.

 

---

🔸 end 🔸

• 재귀를 이용한 분할정복 문제가 올림픽 게임 후로 연속으로 풀어봤는데, 재귀 연습에 좋은 것 같다.
• 문제 분석과 풀이 계획을 적어가며 풀이했다.