[백준] 2630: 색종이 만들기 JAVA

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

---

풀이과정

이 문제는 분할 정복(Divide and Conquer)과탐색을 사용해서 푸는 문제이다.

 

분할 정복

분할 정복이란 하나의 큰 문제를 여러가지로 나눠서 해결하는 것이다. 이 문제는 초반에 NxN 정사각형을 주고 조건에 만족할 때 까지 N/2 x N/2 정사각형 4개로 나눠서 해결한다. 이를 구현하기 위해 재귀함수를 사용한다. (재귀함수 구현 시, stack overflow error가 나지 않도록 주의한다 = 함수 무한 호출 주의)

 

풀이 핵심

1. 입력값을 가져오고, blueCnt와 whiteCnt라는 파란색과 흰색 종이 수를 저장하는 변수를 선언한다.
2. checkColor라는 함수를 선언하여, 배열의 모든 요소가 같은 값을 갖는지에 대한 여부를 boolean값으로 반환시킨다.
3. 재귀함수를 구현한다. 처음에 checkColor를 사용하여 이가 true라면 값에 맞는 counter를 올려주고 아니라면 재귀함수를 4번 호출한다 (x와 y좌표의 시작과 끝 값을 잘 설정할 것)

 

---

최종 코드

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

// The main method must be in a class named "Main".
class Main {
    public static int N;
    public static int blueCnt = 0;
    public static int whiteCnt = 0;
    public static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
               arr[i][j] = Integer.parseInt(st.nextToken()); 
            }
        }
        recur(0, N-1, 0, N-1);
        bw.write(whiteCnt + "\n" + blueCnt);
        bw.flush();
        bw.close();
    }
    public static void recur(int Xstart, int Xend, int Ystart, int Yend){
        if(checkColor(Xstart, Xend, Ystart, Yend)){
            if(arr[Ystart][Xstart] == 0){
                whiteCnt++;
            }else{
                blueCnt++;
            }
            return;
        }
        int midX = (Xstart+Xend)/2;
        int midY = (Ystart+Yend)/2;
        recur(Xstart, midX, Ystart, midY);
        recur(midX+1, Xend, Ystart, midY);
        recur(Xstart, midX, midY+1, Yend);
        recur(midX+1, Xend, midY+1, Yend);
    }

    public static boolean checkColor(int Xstart, int Xend, int Ystart, int Yend){
        int color = arr[Ystart][Xstart];
        for(int row = Ystart; row <= Yend; row++){
            for(int col = Xstart; col <= Xend; col++){
                if(color != arr[row][col]){
                    return false;
                }
            }
        }
        return true;
    }
}