2630번

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

2630번: 색종이 만들기

이 문제는 재귀함수를 이용한 분할 정복이다.

원리는 간단하다. 재귀적으로 종이의 크기를 줄이면서 시작지점을 4곳으로 설정하여 검사를 시행하는 방식이다.

 

예들들어, 8x8크기의 종이가 있다면 처음에 검사를 했을 때, 모든 색이 파란색이거나 흰색이 아니라면 4등분한다.

그런다음, 1,1지점과 1,5지점 5,1지점 5,5지점으로 나누어서 각각을 시작점으로하는 검사를 다시한다.

검사를 했을 때 모두 같은 색이면 그 색의 값을 증가시키고, 그렇지 않다면 다시 재귀함수를 실행하여 모든 부분이 같은 색으로 될때까지 시도한다. 주의 할 점은 그렇게 나누다가 크기가 1이되면 멈추고 그 크기 1의 색깔이 무엇인지 확인하여 값을 증가시킨다. 이 경우는 크기가 1개인 종이가 같은 색을 가졌다고 간주하는 방식이다.

문제에 주어졌던 그림을 보면 이해가 편할 것이다.

 

그럼 이제 코드를 짜보자

먼저 전체 종이의 크기와 종이의 부분별 색깔들을 받아온다.

그 다음, 재귀함수를 호출하여 4등분의 반복을 진행한다.

재귀함수를 구현하는 과정에서 내가 실수를 했던 부분은 시점지점의 지정이였다. 시작지점의 값을 나는 단순히 size/2로 해주었었는데,

이렇게되면 맨처음 4등분은 성립하지만, 그 다음 4등분된 것중에 다시 4등분하는 것의 시작지점은 잘못지정되는 문제가 생긴다.

그렇기 때문에 꼭 원래의 시작지점에 size/2를 더해주어 새로운 시작지점으로 지정해야한다.

package backjoon.b2630;

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

public class b2630 {
    static int white;
    static int blue;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] table = new int[N][N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                table[i][j]= Integer.parseInt(st.nextToken());
            }
        }
        search(0,0,N,table);
        System.out.println(white);
        System.out.println(blue);
    }
    public static void search(int startX,int startY, int size, int[][] table){
        int comp = table[startX][startY];
        if(size==1){
            if(comp==1){
                blue++;
            }
            else white++;
            return;
        }
        for(int i=startX;i<startX+size;i++){
            for(int j=startY; j<startY+size; j++){
                if(table[i][j]!=comp){
                    search(startX,startY,size/2,table);
                    search(startX,startY+size/2,size/2,table);
                    search(startX+size/2,startY,size/2,table);
                    search(startX+size/2,startY+size/2,size/2,table);
                    return;
                }
            }
        }
        if(comp==1){
            blue++;
        }
        else white++;
    }
}