풀이 요약

분할정복이긴 하나 그보단 재귀에 익숙해야 하는 문제

풀이 상세

1. 입력을 받은 후, 분할정복을 시작한다. 나의 경우, 함수에 $R$ 의 시작과 끝 $C$ 의 시작과 끝을 매개변수로 넣어줬다.

2. map 안에서 제 1사분면, 제 2사분면, 제 3사분면, 제 4사분면 순으로 탐색을 한다.

   • 제 1사분면의 경우, $R$ 의 시작과 $C$ 의 끝을 담당하므로 $R$ 의 끝과 $C$ 의 시작을 변경한다.
   • 제 2사분면의 경우, $R$ 의 시작과 $C$ 의 시작을 담당하므로 $R$ 의 끝과 $C$ 의 끝을 변경한다.
   • 제 3사분면의 경우, $R$ 의 끝과 $C$ 의 시작을 담당하므로 $R$ 의 시작과 $C$ 의 끝을 변경한다.
   • 제 4사분면의 경우, $R$ 의 끝과 $C$ 의 끝을 담당하므로 $R$ 의 시작과 $C$ 의 시작을 변경한다.

3. 매개변수에 주어진 인덱스 만큼 탐색을 하며 해당 재귀 실행에서 값이 동일하다면 색종이의 해당 색을 카운팅 해준다.

4. 재귀가 종료되면 각 색깔별 색종이의 수를 출력하면 된다.

코드

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

public class Main {
    static int[][] map;
    static int N;
    static int white, blue;

    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

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

    private static void solve(int r1, int r2, int c1, int c2) {
        if (r1 == N-1 || c1 == N-1 || r2 == 0 || c2 == 0) {
            count(map[r1][c1]);
            return;
        }

        int num = map[r1][c1];
        boolean check = true;
        outer:
        for (int r = r1; r <= r2; r++) {
            for (int c = c1; c <= c2; c++) {
                if (num != map[r][c]) {
                    check = false;
                    break outer;
                }
            }
        }

        if(check) {
            count(num);
            return;
        }

        solve(r1, (r1+r2)/2, (c1+c2)/2+1, c2);
        solve(r1, (r1+r2)/2, c1, (c1+c2)/2);
        solve((r1+r2)/2+1, r2, c1, (c1+c2)/2);
        solve((r1+r2)/2+1, r2, (c1+c2)/2+1, c2);
    }

    private static void count(int num) {
        int tmp = num == 1 ? blue++ : white++;
    }

    public static void main(String[] args) throws Exception {
        input();
        solve(0, N-1, 0, N-1);
        System.out.print(white+ "\n" + blue);
    }
}