[백준] 2630: 색종이 만들기(분할정복)

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

2630번: 색종이 만들기

 

💡 문제 접근 방식 

범위별로 분할해서 재귀 돌리는 형태 -> 분할정복으로 풀어야하는 대표적인 문제

- 기저조건 1: 색종이가 더이상 나눠지지 않을 때 return

-기저조건2: 모든 칸의 색종이 색이 같을 때 return

2. 기저조건 2를 파악하기 위해서는 boolean타입의 확인 절차필요 -> isSame() 함수

3. 1사분면, 2사분면, 3사분면, 4사분면으로 나눠서 재귀돌림 

		// 같은 색깔이 아니라면 자른다
		search(y, x, size / 2);
		search(y + size / 2, x, size / 2);
		search(y, x + size / 2, size / 2);
		search(y + size / 2, x + size / 2, size / 2);

 

💡 전체 코드

package 백준;

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

public class Main_2630 {
	static int[][] map;
	static int N;
	static int zero, one;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static boolean visit[][];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // 입력 끝
		zero = 0;
		one = 0;
		search(0, 0, N);
		System.out.println(zero);
		System.out.println(one);

	}

	private static void search(int y, int x, int size) {
		// 1. 종료조건 1-> 사이즈가 1일 때 자를 수 없음
		if (size == 1) {
			// 1일때-파란색
			if (map[y][x] == 1)
				one++;
			else {
				zero++;
			}
			return;
		}

		// 2. 종료조건: 잘라진 종이가 모두 한가지 색깔로 칠해져있을 때
		if (isSame(y, x, map[y][x], size)) {
			if (map[y][x] == 1)
				one++;
			else {
				zero++;
			}
			return;
		}

		// 같은 색깔이 아니라면 자른다
		search(y, x, size / 2);
		search(y + size / 2, x, size / 2);
		search(y, x + size / 2, size / 2);
		search(y + size / 2, x + size / 2, size / 2);

	}

	private static boolean isSame(int y, int x, int color, int size) {
		for (int i = y; i < y + size; i++) {
			for (int j = x; j < x + size; j++) {
				if (color != map[i][j])
					return false;
			}
		}
		return true;
	}

}