백준 1992. 쿼드트리

문제

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

1992번: 쿼드트리

문제풀이

 구역을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 탐색을 하면서 그 구역이 0이나 1로 되어 있거나 사이즈가 1일 때 탐색을 그만하고 0이나 1을 출력하는 문제였다. 
 구역탐색을 재귀형식으로 시작 행과 시작 열, 사이즈를 받아 탐색을 하는 함수를 만들고, 구역 내에 전부 0이나 1인지 검사하는 check함수를 만들어 사이즈가 1이거나 check함수가 true면 종료하게 만들었다.
 각 레벨에서 여는 괄호로 시작하고, 해당 레벨이 끝나면 괄호를 닫아준다.

소스코드(Java)

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

public class baek1992{
    static char[][] map;
    static int N;
    static StringBuilder answer = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        dfs(0, 0, N);
        System.out.println(answer.toString());

    }

    static void dfs(int sr, int sc, int size) {
        if (size == 1 || check(sr, sc, size)) {
            answer.append(map[sr][sc]);
            return;
        }
        size /=2;
        answer.append("(");
        dfs(sr , sc , size);
        dfs(sr , sc + size, size);
        dfs(sr + size, sc, size );
        dfs(sr + size, sc + size, size);
        answer.append(")");

    }

    private static boolean check(int sr, int sc, int size) {
        char ch = map[sr][sc];
        for (int r = sr; r < sr + size; r++) {
            for (int c = sc; c < sc + size; c++) {
                if (ch != map[r][c]) {
                    return false;
                }
            }
        }
        return true;
    }

}