[백준]2630번. 색종이 만들기(JAVA)

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

---

문제

---

풀이

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

public class Main {

    static int[][] arr;
    static int white, blue;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        arr = new int[n][n];

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

        func(0, 0, n);
        System.out.println(white);
        System.out.println(blue);
    }

    public static void func(int row, int col, int size){
        int count = 0;
        loop:
        for(int i = row; i < row + size; i++){
            for(int j = col; j < col + size; j++){
                if(arr[row][col] == arr[i][j]){
                    count++;
                }else{
                    break loop;
                }
            }
        }

        if(count == size*size){
            if(arr[row][col] == 0){
                white++;
            }else{
                blue++;
            }
        }else{
            size /= 2;
            func(row, col, size);
            func(row+size, col, size);
            func(row, col+size, size);
            func(row+size, col+size, size);
        }
    }
}

 

재귀와 분할정복을 이용한 문제풀이이다.

그렇게 생각한 이유는 다음과 같다.

1. 가장 큰 범위에서 문제가 시작된다.

2. 이후 문제를 조금씩 나누어가며 해결하게 된다.

3. 반복되는 패턴을 갖는다.

 

그렇기에 시작할 때 사이즈와 시작점의 좌표를 준다. 이 후 사이즈에 맞는 좌표들을 모두 탐색하며 비교하게 된다.

만약 비교가 옳지 않다면 즉시 반복을 종료하고 다음 재귀를 호출한다.