백준 BOJ 1992번

---

접근 방법

 

이전에 풀었던 1780번과 유사한 문제다. 다른 점이 있다면 이전에 푼 것은 9분할, 이번 문제는 4분할 한다는 점이다.

https://edvedv.tistory.com/28?category=1038364 

백준 BOJ 1780번

 

똑같이 재귀함수로 분할 정복하면 쉽게 풀 수 있다. 다만 출력을 괄호로 묶어서 하는 것만 신경써주면 된다.

---

코드

import java.util.*;
 
public class Main {
   public static int[][] arr;
   public static StringBuilder sb = new StringBuilder();
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int N = in.nextInt();
      arr = new int[N][N];
 
      for(int i = 0; i < N; i++) {
			String str = in.next();
			
			for(int j = 0; j < N; j++) {
				arr[i][j] = str.charAt(j) - '0';
			}
		}
      QuadTree(0, 0, N);
 
      System.out.println(sb);
      in.close();
   }
   public static void QuadTree(int row, int col, int size){
      if(check(row, col, size)){
         sb.append(arr[row][col]);
         return;
      }
      int next = size / 2;
      sb.append('(');
      QuadTree(row, col, next);								    
		QuadTree(row, col + next, next);
		QuadTree(row + next, col, next);	
		QuadTree(row + next, col + next, next);
      sb.append(')');
   }
   
   // 같은 숫자인지 체크하는 메소드
   public static boolean check(int row, int col, int size) {
      int num = arr[row][col];
 
      for(int i = row; i < row + size; i++){
         for(int j = col; j < col + size; j++){
            if(num != arr[i][j]) return false;
         }
      }
      return true;
   }
}