[백준 2630] 색종이 만들기/ 자바

문제         

레벨: S2
알고리즘: 구현 + 분할정복
풀이시간: 40분
힌트 참조 유무: 무

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

 

1 번째 시도   

[알고리즘 설명]

이 문제는 분할정복 + 구현의 대표적인 문제이다.

직관적으로 나타나 있듯 4개로 나누어 탐색하여야 하고

답을 체킹하는 방식 + 4개로 나누는 방식을 잘 구현해야 한다.

 

필자는 처음 구현할 때 다 나눈 후 답을 체킹하는 방식으로  구현하려고 했다.

그러나 구현에 어려움을 겪어 , 답을 체킹하고 아니면 분할하는 방식으로 구현하였다. 

나처럼 구현에 어려움을 겪는 분들은 이런 식으로 하면 좋을 것 같다.

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

class Main {

    static int white = 0;
    static int blue = 0;

    static int[][] arr;

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

        arr = new int[N][N];
        for(int i = 0; i < N; i++) {
            String[] s = br.readLine().split(" ");
            for(int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
            }
        }

        partition(0,0,N);

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

    public static void partition(int row, int col, int size) {

        if(checkColor(row,col,size)) {
            if(arr[row][col] == 0) {
                white++;
            }
            else {
                blue++;
            }

            return;
        }

        int newSize = size/2;
        partition(row, col, newSize);
        partition(row + newSize, col, newSize);
        partition(row, col +newSize, newSize);
        partition(row + newSize, col + newSize, newSize);

    }

    public static boolean checkColor(int row, int col, int size) {
        int color = arr[row][col];
        
        for(int i = row ; i < row + size; i ++) {
            for(int j = col; j < col + size; j++) {
                if(arr[i][j] != color) 
                    return false;
            }
        }
        
        return true;
    }
}