백준 1992 쿼드트리(Java)

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

1992번: 쿼드트리

---

 

해석 및 팁

 

---

 

이 문제는 백준 2630 색종이 만들기 문제와 상당히 유사한 문제이며 동일하게 분할정복과 재귀를 활용하면 되는 문제입니다. 다만 차이점은 괄호를 더해주어야 한다는 점입니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {

  static int col;
  static int[][] arr;
  static StringBuilder sb = new StringBuilder();
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    arr = new int[n][n];
    
    for(int i = 0; i < n; i++) {
      String str = sc.next();
      for(int j = 0; j < n; j++) arr[i][j] = str.charAt(j) - '0';
    }

    div(0, 0, n);

    System.out.println(sb);
  }

  public static void div(int x, int y, int n) {
    for(int i = x; i < x + n; i++) {
      for(int j = y; j < y + n; j++) {
        col = arr[x][y];
        if(col != arr[i][j]) {
          sb.append("(");
          div(x, y, n / 2);
          div(x, y + n / 2, n / 2);
          div(x + n / 2, y, n / 2);
          div(x + n / 2, y + n /2, n / 2);
          sb.append(")");
          return;
        }
      }
    }
    if(col == 0) sb.append(0);
    else sb.append(1);
  }
}