백준 2346번 분할정복 알고리즘

문제출처 :https://www.acmicpc.net/problem/2630

소스코드

package baekjoon;

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

public class Baek2630 {
    //문제 출처: https://www.acmicpc.net/problem/2630
    static int whiteCnt =0;
    static int blueCnt =0;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        //맵 초기화 해주기
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        divideMap(0,0,n);
        sb.append(whiteCnt).append("\n");
        sb.append(blueCnt);
        System.out.println(sb.toString());
    }
    static void divideMap(int row, int col, int size){
        if (check(row, col, size)) {
            if(map[row][col]==1)
                blueCnt++;
            else whiteCnt++;
            return;
        }
        //split and conquer 시작
        int dividedSize = size/2;
        //나뉜후 왼쪽 위 정사각형
        divideMap(row,col,dividedSize);
        //나뉜후 오른쪽 위 정사각형
        divideMap(row,col+dividedSize,dividedSize);
        //나뉜후 왼쪽 아래 정사각형
        divideMap(row+dividedSize,col, dividedSize);
        //나뉜후 오른쪽 아래 정사각형
        divideMap(row+dividedSize, col+dividedSize, dividedSize);
    }
    static boolean check(int row, int col, int dividedSize) {
        int curColor = map[row][col];
        for (int startRow = row; startRow < row + dividedSize; startRow++) {
            for (int stratCol = col; stratCol < col + dividedSize; stratCol++) {
                if(curColor!=map[startRow][stratCol])return false;
            }
        }
        return true;
    }
}

느낀점 :
오랜만에 풀어본 분할정복 문제였다. 재귀를 이용할 수 있다면, 비교적 쉽게 문제를 풀이 할 수 있을 것이다. 문제를 바라볼 때, 한번에 해결할 수 없고 부분으로 나누어 풀이해야한다면 divide and conquer 알고리즘을 생각해보자