백준 1780 종이의 개수 [JAVA]

문제 해석

• 일단 NxN의 정사각형인 종이를 만들기 위해 N을 첫번째 줄에 입력받는다.
• 입력받았다면 내부 종이의 숫자들을 NxN개 입력받는다.
• -1, 0, 1 모두 같은 숫자로만 이루어질 수 있도록(-1이면 -1만, 0이면 0만, 1이면 1만) 종이를 분할하여 각각의 종이의 개수를 출력하면 되는 문제이다.
• 이 문제는 솔직히 여태까지 풀었던 분할 정복 문제와 크게 다를 바가 없어서 이미 전 포스트에서 설명한 내용은 생략하고 다른 점만 짚고 넘어가고자 한다. (문제 이해가 안된다면 분할 정복 알고리즘, 2630 - 색종이 만들기, 1992-쿼드트리 순으로 한번 쓱 읽어보는 것도 괜찮을 듯 싶다!)
• 크게 다를 점도 없지만 다른 점을 굳이 뽑자면 4분할 -> 9분할인 점이 아닐까 싶다. (아래 참고)
  
  

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int[][] paper; // 종이 내 숫자 구별

    static int minusOne, zero, one = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine()); //영상의 크기

        paper = new int[N][N]; //영상 데이터 구성

        for(int i = 0; i < N; i++){ //종이 내부 숫자 입력받기
            st = new StringTokenizer(br.readLine()); //한줄 식 입력받기

            for(int j = 0; j < N; j++){
                paper[i][j] = Integer.parseInt(st.nextToken()); //띄어쓰기로 쪼개서 입력받기
            }
        }

        br.close();

        cutPaper(0, 0, N);

        System.out.println(minusOne);
        System.out.println(zero);
        System.out.println(one);
    }

    static void cutPaper(int row, int col, int size){

        if(chkPaper(row, col, size)){ //분할한 종이의 내부 숫자들이 모두 같은 숫자이면
            if(paper[row][col] == -1){  // 그 숫자가 -1이면
                minusOne++;
            }else if(paper[row][col] == 0){ // 그 숫자가 0이면
                zero++;
            }else if(paper[row][col] == 1){ // 그 숫자가 1이면
                one++;
            }
        }else { //분할한 숫자가 모두 같은 숫자로만 이루어져 있지 않을 때
            int newSize = size / 3; //전체 종이 사이즈를 9분할로 해야하기 때문에 3x3으로 하므로 사이즈 3

            for (int x = 0; x < size; x += newSize) { //분할한 사이즈만큼 증가시켜서 9분할
                for (int y = 0; y < size; y += newSize) {
                    cutPaper(row + x, col + y, newSize);
                }
            }
        }
    }

    //종이의 내부 숫자가 같은 숫자로만 이루어졌는지 비교
    static boolean chkPaper(int row, int col, int size){
        int data = paper[row][col]; //맨 처음 값으로 비교

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

결과

느낀 점

이 문제 자체는 푸는데 5분도 걸리지 않았지만 시간이 꽤나 많이 나오는 것 같아서 잘 작성한 코드인지는 잘 모르겠다... 그리고 이쯤 되니 분할정복알고리즘 문제 패턴에 대해 꽤 익숙해진 것 같다.