(Java) 백준 쿼드트리 [분할정복, 재귀]

 

 

- 목차

 

함께 보면 좋은 글.

https://westlife0615.tistory.com/46

(Java) 백준 색종이 만들기 [분할정복, 재귀]

 

소개.

아래의 링크는 "백준 쿼리트리" 문제에 대한 웹링크입니다.

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

문제 소개.

 

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

 

 

문제 분석.

쿼드트리 문제는 쿼드트리에 대한 이해도가 필요합니다.

일단 쿼드트리와 관련된 질문은 무조건적으로 분할정복에 대한 케이스라고 생각하시면 되는데요.

2의 제곱수로 주어지는 길이의 정사각형에 대한 분할 정복 문제입니다.

 

1 또는 0 으로 채워진 정사각행렬이 문제로 주어집니다.

그리고 이 정사각행렬을 4분할하여 각 분할된 행렬이 동일한 값들로 채워져있는지 판별해야합니다.

이러한 과정을 재귀적으로 반복합니다.

 

예를 들어,

아래와 같은 길이 8 인 정사각행렬이 있다고 가정하겠습니다.

11110000
11110000
11110000
11110000
00000000
00000000
00000000
00000000

 

이를 쿼드트리 방식으로 탐색하게 되면 아래와 같습니다.

쿼드트리 예시1

 

아래의 예시인 경우의 쿼드트리를 그려보겠습니다.

11110000
11110000
11000000
11000000
00000000
00000000
00000000
00000000

 

쿼드트리 예시 2

 

 

 

문제 풀이.

import java.util.Scanner;

public class Main {


  public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[][] map = new int[n][n];
    scanner.nextLine();
    for (int i = 0; i < n; i++) {
      String line = scanner.nextLine();
      for (int j = 0; j < n; j++) {
        map[i][j] = Integer.parseInt(line.substring(j, j + 1));
      }
    }

    divide(map, 0, 0, n - 1, n - 1);
  }

  static void divide(int[][] map, int startY, int startX, int endY, int endX) {

    if (conquer(map, startY, startX, endY, endX, 1)) {
      System.out.print("1");
      return;
    }
    if (conquer(map, startY, startX, endY, endX, 0)) {
      System.out.print("0");
      return;
    }

    int midY = (startY + endY) / 2;
    int midX = (startX + endX) / 2;
    System.out.print("(");
    divide(map, startY, startX, midY, midX);
    divide(map, startY, midX + 1, midY, endX);
    divide(map, midY + 1, startX, endY, midX);
    divide(map, midY + 1, midX + 1, endY, endX);
    System.out.print(")");
  }

  static boolean conquer(int[][] map, int startY, int startX, int endY, int endX, int value) {
    for (int i = startY; i <= endY; i++) {
      for (int j = startX; j <= endX; j++) {
        if (map[i][j] != value) return false;
      }
    }
    return true;
  }

}

/*
8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

((110(0101))(0010)1(0001))
1100101001010001

*/