[백준] 2630. 색종이 만들기

문제

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

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.
전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

풀이

분할 정복 문제이다. 처음에 재귀문을 돌면서 하얀색 파란색 사각형을 한번에 찾는 코드를 생각했으나 이를 더 작은 문제로 나누어서 특정 색깔 (모두 0 , 모두 1) 로 이루어진 사각형을 찾으면 간단해지는 문제가 된다. 4가지 섹터를 나누어 검사를 한다.
생각한 알고리즘은 다음과 같다.

1. 재귀의 탐색 조건 con 은 0 ,1 로 설정한다. (하얀색 , 파란색 사각형만 찾기 )
2. len/2 == nl(next length)을 설정해 nl만큼 4 섹터를 나눈다.
3. 4섹터 모두 찾는 조건 con 과 일치하면 하나의 사각형으로 이루어져 있으므로 1을 리턴.
4. 4섹터 중 하나도 con과 불일치 부분이 생기면, 해당 부분을 재귀하여 알고리즘 2..4 반복한다.
5. 정답을 리턴한다.

소스코드

import java.io.*;
import java.util.*;
public class dfd {
    static int [][] map ;
    public static void main(String[] args) throws IOException {
        FastReader fr = new FastReader();
        int n = fr.nextInt();
        map = new int[n][n];
        for(int i = 0 ;i < n; i++){
            for(int j = 0 ;j <  n; j++){
                map[i][j] = fr.nextInt();
            }
        }
        //출력 하얀색, 파란색
        int white = helper(n,0,0,0);
        int blue = helper(n,0,0,1);

        System.out.println(white);
        System.out.println(blue);
    }
    public static boolean tracking(int nl, int x, int y, int condition){
        for(int i =x ; i < x+nl; i++){
            for(int j = y; j < y+nl ; j++){
                if(map[i][j] != condition)
                    return false;
            }
        }
        return true;
    }
    //한번 재귀로 흰색 파란색 구하지말고 , 조건 0 , 1이되는 박스를 찾아 개수를 구하는..식.
    public static int helper(int len,int startX, int startY,int condition){
        int nl = len/2;
        if (nl == 0 )
            return 0 ; //끝 도달
        boolean b1 = tracking(nl, startX, startY, condition);
        boolean b2 = tracking(nl, startX+nl, startY,condition);
        boolean b3 = tracking(nl, startX, startY+nl, condition);
        boolean b4 = tracking(nl, startX+nl, startY+nl, condition);

        //만약 절반 나눠서 모두 패스 그러면 1개리턴
        if(b1 && b2 && b3 && b4){
            return 1;
        }else{//아니면 필요한 부분 재귀
            int a = b1 ? 1 : helper(nl, startX,startY,condition);
            int b = b2 ? 1 : helper(nl, startX+nl,startY,condition);
            int c = b3 ? 1 : helper(nl, startX,startY+nl,condition);
            int d = b4 ? 1 : helper(nl, startX+nl,startY+nl,condition);
            //System.out.println("len: "+len+" a b c d"+a+" "+b+" "+c+" "+d);
            return a+b+c+d;
        }

    }


    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}