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

문제

문제 링크

https://www.acmicpc.net/problem/2630

 

문제 설명

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다.

주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

<그림 1>

전체 종이의 크기가 N×N 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다.

나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다.

이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

 

 

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다.

색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.

하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

 

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

 

제한 사항

• N=2k, k는 1 이상 7 이하의 자연수 (N은 2, 4, 8, 16, 32, 64, 128 중 하나이다)

 

입출력 예시

 

 

 

문제 풀이

 

접근 방법

• 한변의 길이가 N인 정사각형의 종이의 색깔이 동일한 색으로 되어있는지 판단해야한다.
  • 첫칸의 색과 모두 동일하면 같은 색
• 동일 색이 아닐 경우 4등분하여 다시 색종이의 색을 확인한다.
• 위의 과정을 재귀함수로 반복한다.

 

코드

import java.io.IOException;
import java.util.List;

public class P_2630 implements Problem {

    // 색 별 종이 개수
    static int blue;
    static int white;

    static boolean[][] paper;

    @Override
    public void exec() throws Exception {

        // 색종이 개수 초기화
        blue = 0;
        white = 0;

        // 전체 종이 크기 입력
        int N = readInt();

        paper = new boolean[N][N];

        // 색종이 입력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (readInt() == 1) paper[i][j] = true;
            }
        }

        // 색종이 자르기
        dividePaper(0, 0, N);

        System.out.print(white+"\n"+blue);

    }

    // 색종이 자르기
    static void dividePaper(int x, int y, int size) {

        // 자를 수 있으면 (색이 모두 같으면)
        if (isSameColor(x, y, size)) {
            // 색 구분해서 카운트
            if (paper[x][y]) {
                blue++;
            } else {
                white++;
            }

            return;
        }

        // 색종이 자르고 1,2,3,4분면 다시 확인
        size /= 2;

        dividePaper(x, y, size);
        dividePaper(x, y + size, size);
        dividePaper(x + size, y, size);
        dividePaper(x + size, y + size, size);
    }

    // 자른 종이의 색이 모두 같은지 판단 함수
    static boolean isSameColor(int x, int y, int size) {

        boolean baseColor = paper[x][y];

        // color 와 다르면 false 반환
        for (int i = x; i < x+size; i++) {
            for (int j = y; j < y+size; j++) {
                if (baseColor != paper[i][j]) return false;
            }
        }
        return true;
    }

    static int readInt() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static List<String> input = List.of(
            "8\n" +
                    "1 1 0 0 0 0 1 1\n" +
                    "1 1 0 0 0 0 1 1\n" +
                    "0 0 0 0 1 1 0 0\n" +
                    "0 0 0 0 1 1 0 0\n" +
                    "1 0 0 0 1 1 1 1\n" +
                    "0 1 0 0 1 1 1 1\n" +
                    "0 0 1 1 1 1 1 1\n" +
                    "0 0 1 1 1 1 1 1"
    );

    public static List<String> output = List.of(
            "9\n" +
                    "7"
    );
}