[BOJ-2630][분할정복] 색종이 만들기 -Java

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

2630번: 색종이 만들기

package algo;

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

public class boj_2630_분할정복 {
	static int cnt[], map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= null;
		
		int N=Integer.parseInt(br.readLine());
		map=new int[N][N];
		cnt=new int[2];
		
		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());
			}
		}
		
		solve(0,0,N);
		System.out.println(cnt[0]);
		System.out.println(cnt[1]);
	}
	private static void solve(int x, int y, int n) {
		//이미 같은색으로 이루어져 있는지 확인!
		
		int check=isEquals(x,y,n);
		if(check==-1) { //4개의 구역으로 나누어서 다시재귀호출
			n/=2;
			for(int i=0; i<2; i++) {
				for(int j=0; j<2; j++) {
					solve(x+n*i, y+n*j, n);
				}
			}
		}
		else cnt[check]++; //만약 다 같다면 해당하는 색종이++
	}
	private static int isEquals(int x, int y, int n) {
		int num=map[x][y];
		
		for(int i=x; i<x+n; i++) {
			for(int j=y; j<y+n; j++) {
				if(num!=map[i][j]) return -1;
			}
		}
		return num;
	}

}

소요시간 : 13분

 

로직을 살펴보면 

 

1. 현재 종이가 다 같은색인지 확인

2. 다 같은 색이라면 그 색깔에 cnt++

3. 다른색이 존재한다면 현재 종이를 4개로 다시 나눈다.

4. 1~3번 반복

 

끝~