[실버 2, 분할정복] 백준 2630 - 색종이 만들기 (자바)

Think

1. 분할정복을 위한 재귀를 만들기 위해서는 기본적으로 매개변수에 [시작Index]와 [size]가 꼭 필요함.

2. 먼저, 전체 사이즈만큼의 2차원 배열을 모두 탐색하면서 해당 크기의 색종이가 모두 파란색인지, 흰색인지 체크 (만약 맞다면 해당 색을 카운트하는 변수 + 1 해주기)

3. 색이 섞여있다면, 4개의 색종이로 분할해준다 (4개의 재귀를 탄다.)

4. (2,3 반복) 하여 값을 도출

 

 

 

제출 코드

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

public class test {
    static int N, map[][], white, blue;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();

        process();

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

    private static void process() {
        recursion(0, 0, N);
    }

    private static void recursion(int startR, int startC, int size) {
        boolean isAllBlue = true;
        boolean isAllWhite = true;

        for (int i = startR; i < startR + size; i++) {
            for (int j = startC; j < startC + size; j++) {
                if (map[i][j] == 0) isAllBlue = false;
                else isAllWhite = false;
            }
        }

        if(isAllBlue){
            blue++;
        }else if(isAllWhite){
            white++;
        }else{
            recursion(startR, startC, size/2);
            recursion(startR, startC + size/2,size/2);
            recursion(startR+size/2, startC,size/2);
            recursion(startR + size/2, startC + size/2,size/2);
        }
    }

    public static void init() throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}

 

 

 

색종이의 색이 모두 같은지 판별하는 다른 방법

private static void recursion(int startR, int startC, int size) {
    int color = map[startR][startC];
    boolean flag = true;

    for (int i = startR; i < startR + size; i++) {
        for (int j = startC; j < startC + size; j++) {
            if(color != map[i][j])  flag = false;
        }
    }

    if(flag){
        if(color == 0){
            white++;
        }else if(color == 1){
            blue++;
        }  
    }else{
        recursion(startR, startC, size/2);
        recursion(startR, startC + size/2,size/2);
        recursion(startR+size/2, startC,size/2);
        recursion(startR + size/2, startC + size/2,size/2);
    }
}

• 처음 위치의 색이랑 나머지 위치의 색이랑 비교해서, 해당 색종이가 모두 같은 색으로 이루어져있는지 판별