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

문제 해석

• 큰 종이(분할 전=원본)의 크기(N)를 입력받아 종이를 쪼개면서 같은 숫자(1 or 0)로만 이루어진 정사각형이 몇개인지 구하면 된다. (단 정사각형은 1(파란색) 0(흰색)의 개수를 따로 세어서 출력한다.)
• 과정을 글로 설명하기 어려워서 그림으로 설명하면 다음과 같다.
  
  
  
  
  
  
• 이렇게 분할 했을 때 같은 수로 이루어진 정사각형을 색깔별로 개수를 구하면 된다.

 if(색종이색체크(row, col, size)){ 
   if(색종이[row][col] == 0){ //흰색이면
       white++; //흰색 색종이 추가
   }else{ //파란색이면
       blue++; //파란색 색종이 추가
   }
   return;
}

• 해당 색종이의 시작점(row, col)으로부터 사이즈에 해당하는 끝점(row+size, col+size)까지의 숫자를 확인하여 같은 숫자로만 이루어져있다면 해당 색을 기준으로 개수를 추가한다.

• 만약, 같은 색으로 이루어지지 않았다면 절반으로 쪼개서(row별, col별) 1~4사분면으로 분할한다.

int mSize = size/2; //절반
        
cutPaper(row, col+mSize, mSize);       //1사분면
cutPaper(row, col, mSize);             //2사분면
cutPaper(row+mSize, col, mSize);       //3사분면
cutPaper(row+mSize, col+mSize, mSize); //4사분면

• 핵심 로직은 위와 같다. 여기까지 이해했다면 코드 작성에 큰 어려움이 없기 때문에 바로 코드로!

코드

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

public class Main {
    static int[][] colorPaper; //정사각형 색종이 색 구별(1과 0으로)

    //흰색, 파란색 색상 카운트할 변수
    static int white = 0;
    static int blue = 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()); //종이의 한 변의 길이 N

        colorPaper = new int[N][N]; //정사각형 색종이 색 구별(1과 0으로)

        for(int i = 0; i < N; i++){ //색종이 내부의 1과 0 입력받기
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < N; j++){
                colorPaper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();

        cutPaper(0, 0, N);

        System.out.println(white);
        System.out.println(blue);
    }

    static void cutPaper(int row, int col, int size){//색종이 탐색 시작점

        if(chkColor(row, col, size)){ //색비교했을 때 정사각형을 이루면 (해당 (row, col, row+size, col+size)의 정사각형이)
            if(colorPaper[row][col] == 0){ //흰색이면
                white++; //흰색 색종이 추가
            }else{ //파란색이면
                blue++; //파란색 색종이 추가
            }
            return;
        }

        int mSize = size/2; //절반 사이즈 (left+right)/2와 같은 역할을 함
        
        cutPaper(row, col+mSize, mSize);            //1사분면
        cutPaper(row, col, mSize);                      //2사분면
        cutPaper(row+mSize, col, mSize);           //3사분면
        cutPaper(row+mSize, col+mSize, mSize); //4사분면
    }

    static boolean chkColor(int row, int col, int size){ //색종이 색 확인
        int color = colorPaper[row][col]; // (row, col)을 기준(처음 색)으로 색 비교

        for(int i = row; i < row+size; i++){
            for(int j = col; j < col+size; j++){
                if(colorPaper[i][j] != color){ //처음 색 기준으로 색이 다르면 (정사각형을 만들 수 X)
                    return false; //다른색이 하나라도 있다면
                }
            }
        }
        
        return true; //모두 같은 색이면
    }
}

결과

느낀 점

색종이 쪼갤 때 4개로 쪼갠다는 생각을 처음에 하지 못해서 문제 푸는데 어려움이 조금 있었다. 2개 분할에 익숙해서 생긴 문제같은데 2개가 아닌 4개로 분할하면 된다는 것을 알게되자마자 문제는 차근차근 풀리기 시작했던 것 같다. 생각을 좀 다양한 방향으로 해야하는데... 익숙하지가 않나보다... (심지어 문제에서도 4개의 색종이로 쪼갠다고 나와있는데... 왜 처음에 생각해내지 못했지...?)