[재귀] 백준 2630번 색종이 만들기 자바 풀이

BOJ 2630번 색종이 만들기 문제 자바(java) 풀이

• 난이도: 실버3
• 백준 2630번 색종이 만들기
  
  
  

문제 정리

1. 여러개의 정사각형칸들로 이루어진 종이가 있으며 파란색 또는 하얀색으로 칠해져있다.
2. 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 종이를 만드려고 한다.
3. 종이가 모두 같은 색으로 칠해져있지 않으면 가로와 세로로 중간 부분을 잘라나간다.
4. 이를 모두 똑같은 색깔의 종이만 남거나 하나 밖에 남지 않을때까지 반복한다.
5. 종이의 크기는 NxN이며 (2,4,8,16,32,64,128) 크기중 하나이다.
6. 하얀색:0, 파란색: 1
7. 최종적으로 하얀색 색종이의 개수와 파란색 색종이의 개수를 출력한다.
   
   
   

문제 접근

어떤 조건을 두고 조건이 만족하지 않으면 계속 반복되는 구조이기 때문에
재귀를 이용하면 되겠다고 생각하였습니다.
조건은 구간을 정하여 그 구간내의 수가 모든 같은 수인지 판별하여
같다면 모두 같은 색이 칠해져 있어서 만족하는 것으로 봅니다.
이를 4개의 4분면으로 나누어서 진행합니다.

문제 풀이

1. 초기 값을 입력받아 배열에 저장합니다.
2. 먼저 초기에 주어진 상태에서 모두 같은 색인지 판별합니다. 모두 같은 색이라면 그 색이 파랑인지? 흰색인지? 판별하여 값을 출력합니다.
3. 모두 같은 색이 아니라면 4개의 4분면으로 나누어 재귀적으로 호출합니다.
   • 1사분면: 1사분면의 x좌표는 0N/2, y좌표는 0N/2 입니다
   • 2사분면: x좌표는 0N/2, y좌표는 N/2N의 범위를 갖습니다
   • 3사분면: x좌표는 N/2N, y좌표는 0N/2의 범위를 갖습니다
   • 4사분면: x좌표는 N/2N, y좌표는 N/2N의 범위를 갖습니다
4. make 함수를 호출하여 다시 그 범위에서 모두 같은 수인지 check 함수를 통해 확인합니다.
   만약 조건을 만족한다면 범위의 첫 색깔을 확인하여 파랑이면 b를 1 증가, 흰색이면 w를 1 증가시킵니다.
   그렇지 않다면 다시 1~4분면의 범위로 나누어서 재귀적으로 계속 탐색해 나갑니다.
   
   
   

추가 예제

8
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1

8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

추가 예제

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

class Main {
    static int N;
    static int[][] paper;
    static int w=0;
    static int b=0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        paper = new int[N][N];
        for(int i=0; i<N; i++){
            String[] temp = br.readLine().split(" ");
            for(int j=0; j<N; j++){
                paper[i][j] = temp[j].charAt(0) - '0';
            }
        }

        if(check(0, N, 0, N)){
            if(paper[0][0] == 1){
                System.out.println("1");
                System.out.println("0");
            }
            else{
                System.out.println("0");
                System.out.println("1");
            }
        }
        else{
            make(0, N/2, 0, N/2, N/2);    // 1사분면
            make(N/2, N, 0, N/2, N/2);    // 2사분면
            make(0, N/2, N/2, N, N/2);    // 3사분면
            make(N/2, N, N/2, N, N/2);    // 4사분면
            System.out.println(w);
            System.out.println(b);
        }

        br.close();
    }

    public static void make(int startX, int endX, int startY, int endY, int len){
        if(!check(startX, endX, startY, endY)){
            make(startX, startX + len/2, startY, startY + len/2, len/2);    // 1사분면
            make(startX + len/2, startX + len, startY, startY + len/2, len/2);    // 2사분면
            make(startX, startX + len/2, startY + len/2, startY + len, len/2);    // 3사분면
            make(startX + len/2, startX + len, startY + len/2, startY + len, len/2);    // 4사분면
        }
        else{
            if(paper[startY][startX] == 1){
                b++;
            }
            else
                w++;
        }
    }

    public static boolean check(int startX, int endX, int startY, int endY){
         int color = paper[startY][startX];

        for(int i=startY; i<endY; i++){
            for(int j=startX; j<endX; j++){
                if(paper[i][j] != color){
                    return false;
                }    
            }
        }
        return true;
    }
}