BOJ#1992 쿼드트리

BOJ#1992 쿼드트리

* 문제

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

* 풀이

- 분할정복을 사용하는 알고리즘들은 대개 3가지의 구성 요소를 갖고 있습니다.

 1. 문제를 더 작은 문제로 분할하는 과정(divide)

 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

(출처 : 알고리즘 문제 해결 전략)

위 해결 전략을 염두하고 문제를 풀어보았습니다.

쉬운 문제이므로 풀이는 생략하겠습니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231992/src/Main.java

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

public class Main {

    static char[][] map = new char[64][64];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < N; i++) {

            String inputLine = br.readLine();
            for (int j = 0; j < N; j++) {

                map[i][j] = inputLine.charAt(j);
            }
        }

        System.out.println(solve(N, map, 0, 0));
    }

    static String solve(int N, char[][] map, int row, int col) {

        // Base Case
        if (N == 1) {

            return "" + map[row][col];
        } else {

            if (isAvailableCompression(N, map, row, col)) {

                return "" + map[row][col];
            }
            // divide & merge
            else {

                String ret = "(";

                for (int i = 0; i < 4; i++) {

                    int newRow = row;
                    int newCol = col;

                    switch (i) {

                        case 0:
                            break;

                        case 1:

                            newCol += N / 2;
                            break;

                        case 2:

                            newRow += N / 2;
                            break;

                        case 3:

                            newRow += N / 2;
                            newCol += N / 2;
                            break;
                    }
                    ret += solve(N / 2, map, newRow, newCol);
                }

                return ret + ")";
            }
        }
    }

    static boolean isAvailableCompression(int N, char[][] map, int row, int col) {

        char data = map[row][col];

        for (int i = row; i < row + N; i++) {
            for (int j = col; j < col + N; j++) {

                if (data != map[i][j]) {

                    return false;
                }
            }
        }

        return true;
    }
}