1780 - 종이의 개수(S2)

문제

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

풀이

간단하게 분할 정복으로 풀 수 있는 문제이다. 분할 정복을 사용하지 않으면 시간 초과 문제가 발생한다.

1. 재귀함수를 사용하여 작은 범위로 나눈다.
2. 나눈 범위를 카운팅하며 예외(다른 숫자)가 발생할 시 다음 단계로 분할하고, 아니라면 모두 카운팅 후 값을 증가시킨다.

코드

import java.util.*;
import java.io.*;

/*
 분할 정복 사용. 자세한 것은 세부 주석 참조.
*/

public class Main {
    static int[][] board;
    static int res[] = {0, 0, 0}; // -1, 0, 1
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        board = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        cut(0, 0, N, N, N);

        for (int i = 0; i < 3; i++) {
            bw.write(res[i] + "\n");
        }
        bw.close();
    }

    private static void cut(int sR, int sC, int eR, int eC, int size) {

        //1. 해당 종이가 일체인지 판단
        boolean isSame = true; //true로 유지될 경우 해당 종이는 같은 수로 되어있음
        int check = board[sR][sC]; //확인용 변수
        SameCheck:
        for (int i = sR; i < eR; i++) {
            for (int j = sC; j < eC; j++) {
                if(board[i][j] != check) {
                    isSame = false;
                    break SameCheck;
                }
            }
        }

        //2. 같다면 카운팅 후 리턴
        if(isSame) {
            res[check + 1] += 1;
            return;
        }

        //3. 아니라면 1/3로 분할
        int newSize = size / 3;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cut(sR + i * newSize, sC + j * newSize, sR + (i + 1) * newSize, sC + (j + 1) * newSize, newSize);
            }
        }
        /* 위 반복문은 다음과 같음
        cut(sR  + 0 * newSize, sC + 0 * newSize, sR + 1 * newSize, sC + 1 * newSize, newSize);
        cut(sR  + 0 * newSize, sC + 1 * newSize, sR + 1 * newSize, sC + 2 * newSize, newSize);
        cut(sR  + 0 * newSize, sC + 2 * newSize, sR + 1 * newSize, sC + 3 * newSize, newSize);

        cut(sR  + 1 * newSize, sC + 0 * newSize, sR + 2 * newSize, sC + 1 * newSize, newSize);
        cut(sR  + 1 * newSize, sC + 1 * newSize, sR + 2 * newSize, sC + 2 * newSize, newSize);
        cut(sR  + 1 * newSize, sC + 2 * newSize, sR + 2 * newSize, sC + 3 * newSize, newSize);

        cut(sR  + 2 * newSize, sC + 0 * newSize, sR + 3 * newSize, sC + 1 * newSize, newSize);
        cut(sR  + 2 * newSize, sC + 1 * newSize, sR + 3 * newSize, sC + 2 * newSize, newSize);
        cut(sR  + 2 * newSize, sC + 2 * newSize, sR + 3 * newSize, sC + 3 * newSize, newSize);
        */
    }
}