백준 2630번 : 색종이 만들기

 문제

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

2630 색종이 만들기

 

 구현 방법

 전형적인 분할정복 문제입니다.

분할정복이란 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘입니다.

색종이의 맨 값을 저장해준 다음 탐색하면서 저장 값과 다르면 4등분으로 나눠줍니다.

이를 반복해줍니다.

 

 구현 코드

package BOJ.Silver;

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

public class B2630_색종이만들기 {
	static int N, blue, white;
	static int[][] arr;
	static boolean flag;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
			}
		}
		// 입력완료
		divide(0, 0, N);
		System.out.println(white+"\n"+blue);
	}
	
	static void divide(int r, int c, int length) {
		flag = false;
		int temp = arr[r][c]; // 처음 값 저장
		
		stop:for (int i=r;i<r+length;i++) {
			for (int j=c;j<c+length;j++) {
				if (arr[i][j]!=temp) { // 값이 다르다면
					flag = true;
					break stop;
				}
			}
		}
		if (!flag) { // 값이 같을 때
			if (temp==1) blue++;
			else white++;
			return;
		}
		if (flag) { // 값이 다를 때
			int size = length/2; // 길이를 반으로 나눠주고
			divide(r, c, size); // 좌측 위
			divide(r, c+size, size); // 우측 위
			divide(r+size, c, size); // 좌측 아래
			divide(r+size, c+size, size); // 우측 아래
		}
	}
}

 

정답!