[백준 1992] 쿼드트리 - JAVA

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

 

분할 정복 문제

 

배열이 같은 숫자로만 이뤄져있다면  0 or 1을 추가한다.

아니라면, "(" + 4분면 분할정복 값 + ")" 으로 채운다.

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

class Main {

  static StringBuilder sb = new StringBuilder();
  static int N, m[][];

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());

    m = new int[N][N];
    for (int i = 0; i < N; i++) {
      String s = br.readLine();
      for (int j = 0; j < N; j++) {
        m[i][j] = s.charAt(j) - '0';
      }
    }

    solve(0, N, 0, N);
    System.out.println(sb);
  }

  static void solve(int sr, int er, int sc, int ec) {

    int zero = 0, one = 0;
    for (int r = sr; r < er; r++) {
      for (int c = sc; c < ec; c++) {
        if (m[r][c] == 0) {
          zero++;
        } else {
          one++;
        }
      }
    }

    if (one == 0) {
      sb.append(0);
    } else if (zero == 0) {
      sb.append(1);
    } else {

      // 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
      int hr = (er + sr) / 2;
      int hc = (ec + sc) / 2;
      sb.append("(");
      solve(sr, hr, sc, hc);
      solve(sr, hr, hc, ec);
      solve(hr, er, sc, hc);
      solve(hr, er, hc, ec);
      sb.append(")");
    }
  }
}