우매함의 봉우리를 넘어서며 개발하면서 기록하기

백준 1992. 쿼드트리

03 Mar 2021

문제 바로가기

쿼드트리

문제 요약

흑백 영상에서 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어져있는 영상이 있다.

BJ_1992

이런 그림에서 같은 숫자들의 점이 한곳에 많이 몰려 있으면 압축해서 표현할 수 있다.

BJ_1992(2)

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 이렇게 4개 영상으로 나누어 압축해서 괄호 안에 묶어서 표현해보자.

문제 풀이 포인트

이 문제의 가장 핵심 포인트는 4부분으로 나누어 확인하는 것이다. 4분할의 한 분면에서 0과 1이 섞여 있다면 계속해서 잘라 나가 검증해야 하므로 분할탐색을 사용한다.

분할 탐색 기법은 분할 - 정복 - 결합의 과정을 거치는데 분할하는 과정에서 재귀를 사용하여 문제를 해결한다. 코드의 자세한 부분은 주석을 통해 달아놓았다.

문제 코드[JAVA]

코드 펼치기 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  static int[][] map;
  static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
  public static void main(String[] args) throws IOException {
    
    StringTokenizer st = new StringTokenizer(in.readLine());
    int N = Integer.parseInt(st.nextToken());
    
    map = new int[N][N];
    
    for(int i = 0; i < N; i++) {
      String str = in.readLine();
      for(int j = 0; j < N; j++) {
        map[i][j] = Integer.parseInt(str.substring(j, j+1));
      }
    }
    func(0, 0, N);
    out.flush();
    out.close();
    in.close();
  }
  // 입력받은 사이즈에서 반씩 줄여나가기
  // 입력받은 좌표는 잘린 상자의 제일 왼쪽 위
  private static void func(int x, int y, int size) throws IOException {
    // 잘린 점의 크기가 1일경우 그 점의 값을 적고 리턴
    if(size == 1) { 
      out.append(map[x][y] + "");
      return;
    }
    // 전체 값이 다 같은지 확인하고
    // 같으면 그 값을 적어주고 리턴
    // 같지 않으면 쪼개기 진행
    
    // 1. 전체 값이 같은지 확인
    boolean flag = true;
    int first = map[x][y];
    for(int i = x; i < x + size; i++) {
      L:for(int j = y; j < y + size; j++) {
        if(map[i][j] != first) {
          flag = false;
          break L;
        }
      }
    }
    // 2.  전체 값이 같다면 적고 리턴
    if(flag) {
      out.append(first+ "");
      return;
    }
    // 3. 전체 값이 같지 않다면 쪼개기
    // 시작할때 괄호 열기로 시작하니까 괄호 먼저 써주기
    out.append("(");
    for(int i = 0; i < 2; i++) {
      for(int j= 0; j < 2; j++) {
        func(x + size/2*i, y + size/2*j, size/2);
      }
    }
    // 끌나면 괄호닫기
    out.append(")");

  }
}

Related posts