<Algorithm> 189. 쿼드트리(BJO)

1. 1992번 쿼드트리(BJO)

   사용 알고리즘 :  분할정복

• 분할정복을 잘 이해했는지 확인하기 위해 한문제 더 풀어보았다. 문제가 살짝 난해하다는 느낌이 있는데 해보면 별다를게없는 문제이다.

• 마지막에 출력이 쿼드트리 형태로 나와야하기 때문에 이부분이 헷갈렸지만 분할로직의 진행과정을 이해했다면 금방 풀수 있는 부분이다.

• 출력형태가 파고드는게 아닌 옆으로 진행되었다면 쉽지 않았을 것 같다.

문제에 대한 접근&생각

1. 배열을 4등분해서 분할된 배열의 원소가 같아야함 -> 분할정복!

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    static int map[][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        /***************************
         * 배열을 4등분 하면서 탐색한다.
         * 하나의 숫자로 이루어저있는지 체크
         * 아니면 분할하는 방식으로 값을 구한다.
         ***************************/
        map = new int[n][n];
        for(int i = 0; i < n; i++) {
          char[] temp = br.readLine().toCharArray();
          for(int j = 0; j < temp.length; j++) {
              map[i][j] = temp[j] - '0';
          }
        }
        solve(0, 0, n);
        System.out.println(res);
    }
    static String res="";
    private static void solve(int x, int y, int n) {
        
        if(isSame(x, y, n)) {
            res+=map[x][y];
            return;
        }else {
            res+="(";
        }
        
        int div = n/2;
        
        for(int i = 0; i < 2; i++) {
          for(int j = 0; j < 2; j++) {
              solve(x+i*div, y+j*div, div);
           }
        }
        res+=")";
    }
    private static boolean isSame(int x, int y, int n) {
        for(int i = x; i < x + n; i++) {
          for(int j = y; j < y + n; j++) {
              if(map[i][j] != map[x][y]) return false;
          }
        }
        return true;
    }
    
}