/ BOJ

BOJ_2630_색종이만들기_JAVA

문제 : 색종이만들기

링크 : BOJ_2630_색종이만들기

접근 방식

주어진 배열에서, 배열이 모든 같은 수로 이루어질 때까지 4분할 시킨다. 계속해서 분할된 모든 배열이 같은 수로 이루어져 있을 때, 서로 다른 사각형의 수를 구하면 된다.

이 문제는 대표적인 분할정복 문제이다.

풀이 방법

  1. 먼저 배열의 크기를 읽어와 변수 N에 저장하고, N*N크기의 배열을 생성해 배열에 입력값을 할당한다.

  2. 분할정복 알고리즘을 적용한다. 메서드의 인자값으로는 x,y 좌표값 그리고 배열의 크기 N을 받는다.

  3. 개수를 카운트할 변수를 하나 생성하고, 배열을 탐색하며 배열의 모든 수를 카운트 변수에 더한다.

  4. 배열 탐색이 끝나고 카운트 수가 N*N이라면 1 만으로 이루어진 사각형이고, 0이라면 0 만으로 이루어진 사각형이다. 둘다 아니라면 1과 0이 섞여있는 사각형이므로, 4분할시켜 재귀호출한다.

  5. 1 만으로 이루어진 사각형과 0 만으로 이우러진 사각형의 갯수를 각각 더하여 순서대로 출력해준다.

소스 코드


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

public class BOJ_2630_색종이만들기 {
	static int[][] arr;
	static int zero, one;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());
		arr = new int[N][N];
		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		cut(0, 0, N);
		System.out.println(zero);
		System.out.println(one);

	}

	public static void cut(int x, int y, int N) {
		int cnt = 0;

		// 해당 범위가 모두 같은 값을 가지는 지 체크
		for (int i = x; i < x + N; i++) {
			for (int j = y; j < y + N; j++) {
			// 배열을 탐색하며 모두 더한다.(각각의 시작 좌표 x,y에서 x+N, y+N까지)
				cnt += arr[i][j];
			}
		}

		// 모두 더한 수가 N*N이라면 해당 범위가 모두 1이다.
		if (cnt == N * N) {
			one++;
		// 모두 더한 수가 0이라면 해당 범위에는 모두 0이 들어가있다.
		} else if (cnt == 0) {
			zero++;
		// 둘다 아닌경우 0과 1이 섞여있으므로 4분할하여 재귀해준다.
		} else {
			int half = N / 2;
			cut(x, y, half);
			cut(x + half, y, half);
			cut(x, y + half, half);
			cut(x + half, y + half, half);
		}

	}

}