[BOJ 1992] 쿼드트리 (Java)

문제

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

1992번: 쿼드트리

BOJ1992 쿼드트리

풀이

분할정복으로 푼다. 

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 사분면 순으로 재귀함수를 호출하면서 

모든 숫자가 1이면 1 출력, 0이면 0 출력. 이외의 케이스는 좌표와 크기를 갱신하여

다시 재귀를 돌려주면 된다.

 

2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java)

[BOJ 2630] 색종이 만들기 (Java)

 

소스코드

package dp;

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

public class BOJ1992 {

    public static int oneCnt, zeroCnt;
    public static int[][] arr;
    public static StringBuilder sb;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        oneCnt = 0;
        zeroCnt = 0;
        sb = new StringBuilder();
        for(int i = 1; i <= N; i++){
            String s = br.readLine();
            for(int j = 1; j <= N; j++){
                arr[i][j] = Integer.parseInt(String.valueOf(s.charAt(j-1)));
            }
        }

        divide(1, 1, N);
        System.out.println(sb.toString());
    }

    private static void divide(int x, int y, int N){
        int cnt = 0;
        for(int i = x;  i < x+N; i++ ){
            for(int j = y; j < y+N; j++){
                if(arr[i][j] == 1){
                    cnt++;
                }
            }
        }
        if(cnt == N*N){
            sb.append(1);
        } else if(cnt == 0){
            sb.append(0);
        } else {
            sb.append("(");
            divide(x, y, N/2); // up-left
            divide(x,y+N/2, N/2); // up-right
            divide(x+N/2, y, N/2); // down-left
            divide(x+N/2, y+N/2, N/2); //down-right
            sb.append(")");
        }

    }
}