백준 1780 종이의 개수 Java: 9분할 재귀와 종료 조건

백준 1780번은 한 영역이 모두 같은 수인지 확인하고, 아니라면 같은 크기의 아홉 영역으로 나누는 분할 정복 문제다. 원문에는 풀이와 디버깅을 합쳐 약 22분 40초가 걸렸고, 중첩 반복문의 변수를 잘못 써 시간을 보냈다고 기록돼 있다.

• 백준 1780번 종이의 개수

구현의 중심은 재귀 호출보다 한 영역의 좌표와 크기를 일관되게 정의하는 것이다.

재귀 함수가 맡을 한 가지 일

divide(row, col, size)는 (row, col)에서 시작하는 size × size 영역을 처리한다.

1. 영역의 모든 값이 왼쪽 위 값과 같으면 해당 숫자의 개수를 1 늘리고 끝낸다.
2. 하나라도 다르면 size / 3 크기의 아홉 영역을 재귀 호출한다.

크기가 1인 영역은 반드시 같은 값으로만 이루어진다. 따라서 size == 1을 따로 처리하지 않아도 ‘모두 같은가’ 검사가 자연스럽게 종료 조건이 된다.

값은 -1, 0, 1뿐이다. 배열 index로는 value + 1을 사용하면 조건문 세 개를 반복하지 않아도 된다.

Java 코드

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

public class Main {
    private static int[][] paper;
    private static final int[] count = new int[3];

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int size = Integer.parseInt(reader.readLine());
        paper = new int[size][size];

        for (int row = 0; row < size; row++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int col = 0; col < size; col++) {
                paper[row][col] = Integer.parseInt(tokenizer.nextToken());
            }
        }

        divide(0, 0, size);

        System.out.println(count[0]);
        System.out.println(count[1]);
        System.out.println(count[2]);
    }

    private static void divide(int startRow, int startCol, int size) {
        int value = paper[startRow][startCol];

        if (isUniform(startRow, startCol, size, value)) {
            count[value + 1]++;
            return;
        }

        int nextSize = size / 3;
        for (int rowPart = 0; rowPart < 3; rowPart++) {
            for (int colPart = 0; colPart < 3; colPart++) {
                divide(
                        startRow + rowPart * nextSize,
                        startCol + colPart * nextSize,
                        nextSize
                );
            }
        }
    }

    private static boolean isUniform(
            int startRow,
            int startCol,
            int size,
            int expected
    ) {
        for (int row = startRow; row < startRow + size; row++) {
            for (int col = startCol; col < startCol + size; col++) {
                if (paper[row][col] != expected) {
                    return false;
                }
            }
        }
        return true;
    }
}

좌표 실수를 줄이는 방법

분할 정복 코드는 짧지만 row, col, size가 섞이면 정상적으로 실행되면서도 일부 영역을 잘못 볼 수 있다.

• 모든 구간을 반열린 범위 [start, start + size)로 쓴다.
• 행 반복문에는 row, 열 반복문에는 col만 쓴다.
• 아홉 자식의 시작점은 start + part × nextSize 한 식으로 만든다.
• 카운트 순서 -1, 0, 1과 배열 index의 변환을 한 곳에 둔다.

원문에서 겪은 중첩 반복문 변수 실수는 알고리즘보다 좌표 규칙의 문제였다. 재귀 호출식을 외우기보다 영역의 계약부터 고정하는 편이 디버깅에 도움이 된다.

지수를 절반으로 나누는 다른 분할 정복은 백준 1629 곱셈, 재귀 호출의 반환 시점을 점검하는 예시는 백준 25501 재귀의 귀재에서 이어서 볼 수 있다.

검증 범위

Java source를 수동 검토했다. 크기 1, 전체가 같은 종이, 아홉 영역만 서로 다른 종이와 작은 무작위 3ⁿ × 3ⁿ 종이를 명시적 stack 기반 기준 구현과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.