[백준 1992번] 쿼드트리 :: 늦깎이 IT

[백준 1992번] 쿼드트리 URL

분할정복의 정석(?)같은 느낌의 문제입니다. 비슷하지만 꼭 비슷하지않은 문제도 참고해보시기 바랍니다.

2019/03/21 - [알고리즘 문제/알고스팟] - [알고스팟] 쿼드 트리 뒤집기 :: 늦깎이 IT

[풀이 방법]

1. 현재 맵이 한 가지색으로 칠해져 있는지 확인한다.

 - 한 가지색으로 칠해져 있다면 답을 출력한다.

2. 한 가지색으로 칠해져 있지 않다면, 현재 맵을 가로 2등분, 세로 2등분으로 총 4조각으로 나눈다.

3. 각각의 조각 (왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래)에 대해 다시 DFS 탐색을 시작한다.

 - 결국 1 X 1 칸은 한 가지색으로 칠해져 있을 수 밖에 없으므로 이를 기저조건으로 삼는다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N;
    static int[][] map;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        map = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(str.charAt(j) + "");
            }
        }
        dfs(0, 0, N);
    }
 
    public static void dfs(int row, int col, int size) {
 
        if (isPossible(row, col, size)) {
            System.out.print(map[row][col]);
        } else {
            System.out.print("(");
            int newSize = size / 2;
            dfs(row, col, newSize);
            dfs(row, col + newSize, newSize);
            dfs(row + newSize, col, newSize);
            dfs(row + newSize, col + newSize, newSize);
            System.out.print(")");
        }
    }
 
    public static boolean isPossible(int row, int col, int size) {
 
        int black = 0;
        int white = 0;
 
        for (int i = row; i < row + size; i++) {
            for (int j = col; j < col + size; j++) {
                if (map[i][j] == 1)
                    black += 1;
                else
                    white += 1;
 
                if (black > 0 && white > 0)
                    return false;
            }
        }
        return true;
 
    }
 
}