[백준 Java]_색종이 만들기 (2630)

문제 정보

• 출처 및 난이도: 백준 실버2
• 링크: https://www.acmicpc.net/problem/2630
• 분류: 분할 정복, 재귀

---

문제 요약

N×N 크기의 색종이를 잘라 하얀색(0) 또는 파란색(1) 단색 종이로 만들 때,
각각 몇 장이 나오는지 출력하는 문제.
한 구역이 단색이 아니면 4등분해서 재귀적으로 반복.

---

풀이 접근

1. 전체 N×N 구역이 단색인지 확인 (hasSameColor)
2. 단색이면 색상에 따라 white 또는 blue 카운트 증가 후 종료
3. 단색이 아니면 size/2 로 4등분하여 각각 재귀 호출
4. N은 항상 2의 거듭제곱으로 주어지므로 size/2가 정확히 나눠떨어짐

---

핵심 아이디어

• 쿼드 트리(Quad Tree) 구조: 조건 불만족 시 4개의 자식으로 분할하는 분할 정복
• hasSameColor로 기저 조건 판별 → 같으면 카운트, 다르면 4분할 재귀
• 정사각형의 시작 좌표 (n, m)과 size만으로 모든 구역을 표현 가능

---

코드

import java.util.Scanner;

class Main {
    static int[][] square;
    static int white = 0;
    static int blue = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        square = new int[N][N];

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                square[i][j] = scanner.nextInt();

        div(0, 0, N);
        System.out.println(white);
        System.out.println(blue);

        scanner.close();

    }

    static boolean hasSameColor(int n, int m, int size) {
        int color = square[n][m];
        for (int i = n; i < n + size; i++)
            for (int j = m; j < m + size; j++)
                if (square[i][j] != color) return false;
        return true;
    }

    static void div(int n, int m, int size) {
        if (hasSameColor(n, m, size)) {
            if (square[n][m] == 0) white++;
            else blue++;
            return;
        }
        int div = size / 2;
        div(n, m, div);
        div(n,m + div, div);
        div(n + div, m, div);
        div(n + div, m + div, div);
    }

    /*
    n/2씩 사각형 만들고
    각 사각형에 대해 색상 확인하고 (hasSameColor)
    같으면 사각형 + 1 다르면 다시 재귀
     */

}

---

배운 점 / 회고

• 분할 정복의 전형적인 패턴을 익힌 문제인데, 개인적으로 재귀는 언제나 어렵게 느껴진다.
• hasSameColor 를 별도 메서드로 분리하니 div 로직이 훨씬 읽기 쉬워짐
• N이 2의 거듭제곱임을 보장해주기 때문에 size/2 나눗셈에서 홀수 처리를 따로 안 해도 되서 그나마 편했다.