[백준]1992번. 쿼드트리(JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;

public class Main {

    static int[][] arr;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        arr = new int[n][n];

        for(int i = 0; i < n; i++){
            String str = br.readLine();
            for(int j = 0; j < n; j++){
                arr[i][j] = Integer.parseInt(str.substring(j,j+1));
            }
        }
        sb = new StringBuilder();

        func(0, 0, n);

        System.out.println(sb.toString());
    }

    public static void func(int row, int col, int size){
        int count = 0;
        loop:
        for(int i = row; i < row + size; i++){
            for(int j = col; j < col + size; j++){
                if(arr[row][col] == arr[i][j]){
                    count++;
                }else{
                    break loop;
                }
            }
        }

        if(count == size*size){
            if(arr[row][col] == 0){
                sb.append("0");
            }else{
                sb.append("1");
            }
        }else{
            sb.append("(");
            size /= 2;
            func(row, col, size);
            func(row, col+size, size);
            func(row+size, col, size);
            func(row+size, col+size, size);
            sb.append(")");
        }
    }
}

 

재귀를 이용한 분할정복 문제이다. 

풀이법을 생각한 이유는 다음과 같다.

 

1. 문제 풀이 범위가 전체->극소로 줄어든다.

2. 경향성이 있는 범위에 대한 문제로 주어진다.

3. 풀이법이 동일하다.

 

따라서 색상에 대한 체크를 진행한 후에 조건을 만족하지 않는다면 양쪽에()를 추가하고 그 사이에 재귀적으로 탐색을 진행한다.

이때, 문제에서 좌상단, 우상단, 좌하단, 우하단으로 순서가 주어졌기 때무에 재귀의 순서를 필수적으로 맞추어줘야 한다.