[BOJ] 1780 종이의 개수

종이의 개수

풀이

• -1,0,1 로 채워져 있는데, 종이가 모두 같은 수로 되어 있지 않으면, 같은 크기의 종이 9개 로 자르고, 잘린 종이에 대해 종이가 모두 같은 수로 이루어질 때 까지 반복한다.
• -1로만 채워진 종이 개수, 0으로만, 1로만 채워진 종이개수 각각 구해라.
• 재귀함수를 써야 겠다고 생각. 일단 색이 다 같은지 확인하고, 다 같지 않다면! 9등분으로 나눈 부분등을 하나씩 재귀를 돌린다. 이 때, 9등분이므로 사이즈는 지금사이즈/3 으로 줄어들게 된다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    static int zeroA = 0,oneA=0,minuA=0;
    static int N;
    static int[][] map;
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        StringTokenizer st;
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        cur(N,0,0);
        System.out.println(minuA);
        System.out.println(zeroA);
        System.out.println(oneA);
    }
    private static void cur(int k,int i, int j){
        //색이 다 같으면
        boolean isFind = true;
        int start = map[i][j];
        L:for(int l=i;l<i+k;l++){
            for(int m=j;m<j+k;m++){
                if(start!=map[l][m]){
                    isFind = false;
                    break L;
                }
            }
        }
        if(!isFind){
            //다 같지 않으면
            int newSize = k/3;
            //9개 recusive
            cur(newSize,i,j);
            cur(newSize,i,j+newSize);
            cur(newSize,i,j+newSize*2);
            cur(newSize,i+newSize,j);
            cur(newSize,i+newSize,j+newSize);
            cur(newSize,i+newSize,j+newSize*2);
            cur(newSize,i+newSize*2,j);
            cur(newSize,i+newSize*2,j+newSize);
            cur(newSize,i+newSize*2,j+newSize*2);
        }
        else{
            if(start==0) zeroA++;
            else if(start==1) oneA++;
            else minuA++;
        }
    }
}

• 나는 처음에 이렇게 재귀를 안돌리고, 2중 for문으로 돌렸는데 사실 똑같긴하다. 이런식으로.
  
  아무튼 저 코드 방식으로 재귀 돌리는 문제가 분할정복에 꽤 많이 등장하는 거 같다. 익혀두기!!