BOJ_S3_2630

📁 [S3_2630] 색종이 만들기

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


public class Main {
    static StringTokenizer st;
    static int[][] arr;
    static int zero,one;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 종이 크기
        int N = Integer.parseInt(br.readLine());
        
        arr = new int[N][N];
        
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 0 으로 초기화
        zero = 0;
        one = 0;

        go(0,0,N);

        sb.append(zero).append("\n");
        sb.append(one);

        System.out.println(sb);
    }

    static void go(int row, int col, int size){
        // 다 똑같으면
        if(check(row, col, size)){
            // 같은 값이 0 일때
            if(arr[row][col] == 0){
                zero++;
            }
            // 같은 값이 1 일때
            else{
                one++;
            }
            return;
        }
        // 다르면 재귀
        else{
            size /= 2;

            // 왼쪽 위
            go(row,col,size);

            // 오른쪽 위
            go(row,col+size,size);

            // 왼쪽 아래
            go(row+size,col,size);

            // 오른쪽 아래
            go(row+size,col+size,size);
        }
    }


    // 같은 수 인지 아닌지 검사
    static boolean check(int row, int col, int size){

        int first = arr[row][col];
        for(int i=row; i<row+size; i++){
            for(int j=col; j<col+size; j++){
                if(arr[i][j] != first){
                    return false;
                }
            }
        }
        return true;
    }
}

🤔 나의 생각

최근에 풀었던 S2_1780 문제와 같은 유형의 문제이다.
그래서 손쉽게 풀 수 있었다.
이 문제는 4등분을 하기 때문에 경우가 더 적었다. check() 메서드를 통해 범위 안에 값들이 다 같은 값인지 확인하고 같은 값이면 true, 다른 값이면 false를 반환하였다.
그리고 go() 메서드로 check() 를 통해 true면 그 수가 0인지 1인지 확인하고 카운팅을 해줬다.
만약 false 면 4등분을 해주고 재귀를 실행하였다. size 를 2로 나누어 그 값을 통해 go()를 다시 호출해주었다.
최근에 푼 문제의 유형을 다시 풀어서 맞추니 기분이 아주 좋았다.