[BOJ 2650] 백준 2650 색종이 만들기

문제

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

2630번: 색종이 만들기

풀이

분할정복문제였다.

현재 위치부터 ~ 그래프 길이 끝 (N) 의 색깔이 동일하다면 색종이 하나로 표현 가능하다.

그게 아니라면, N/2 로 현재위치~ N/2 위치 까지 색깔 비교

분할한 후에, 4 구역으로 나눠서 색깔 비교 진행

import java.util.Scanner;

public class Main {
    public static int[][] maps;
    public static int white = 0;
    public static int blue = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        maps = new int[N][N];

        for (int i = 0; i< N; i++){
            for (int j=0; j<N; j++){
                maps[i][j] = in.nextInt();
            }
        }

        divide_maps(0, 0, N);

        System.out.println(white);
        System.out.println(blue);
    }

    public static void divide_maps(int r, int c, int N){
        boolean division = true;
        for (int i = r; i < r + N; i++){
            for (int j = c; j < c + N; j++){
                if (maps[i][j] != maps[r][c]){
                    division = false;
                    break;
                }
            }
            if (!division){
                break;
            }
        }

        if (division){
            if (maps[r][c] == 0){
                white ++;
            }
            else {
                blue++;
            }
            return;
        }

        int new_N = N/2;
        divide_maps(r, c, new_N); // 왼쪽 위
        divide_maps(r, c + new_N, new_N); // 오른쪽 위
        divide_maps(r + new_N, c, new_N); // 왼쪽 아래
        divide_maps(r + new_N, c + new_N, new_N); // 오른쪽 아래
    }
}

 

아쉬웠던점

구역의 모든 색깔이 모두 같은지 비교하는 부분에서,

i는 r 부터, j는 c 부터 진행해야하는데 0부터 진행해서 계속 무한루프가 돌았다.