164. 2630 (색종이 만들기) - 자바

import java.util.*;
import java.io.*;

class Main {
	static int[][] paper;
	static int cnt0;
	static int cnt1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		paper = new int[N][N];
		cnt0 = 0;
		cnt1 = 0;

		for (int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				paper[i][j] = Integer.parseInt(tmp[j]);
			}
		}

		find(0, 0, N);
		System.out.println(cnt0);
		System.out.println(cnt1);

	}

	private static void find(int x, int y, int N) {
		int color = paper[x][y];
		for (int i = x; i < x + N; i++) {
			for (int j = y; j < y + N; j++) {
				if (color != paper[i][j]) {
					find(x, y, N / 2);
					find(x, y + N / 2, N / 2);
					find(x + N / 2, y, N / 2);
					find(x + N / 2, y + N / 2, N / 2);
					return;
				}
			}
		}
		if(color == 0) cnt0++;
		else cnt1++;	
	}
}

문제요약

N*N 이 같은 색인 색종이를 만들어라

설명

분할정복에 대해서는 아래를 참고하자.

https://smhope.tistory.com/432?category=1056187 

[알고리즘 | 자료구조] 분할정복

먼저 그림을 통해서 문제를 이해해보자.

이미지 출처:  https://st-lab.tistory.com/227

위와 같이 N*N이 같은 색상이 되도록 분할로 처리한다.

 

각 사분면을 나누기 위해서 아래 식을 사용할 것이다.

					find(x, y, N / 2);
					find(x, y + N / 2, N / 2);
					find(x + N / 2, y, N / 2);
					find(x + N / 2, y + N / 2, N / 2);

순서대로 1사분면, 2사분면, 3사분면, 4사분면으로 그림으로 나타내면 다음과 같다.

다시말해 현재 4사분면과 같이 완벽한 N*N사각형이 되지 않는이상 계속해서 나눌 것이다.

 

int color = paper[x][y];

먼저 각 사분면 첫부분을 color로 지정한다.

		for (int i = x; i < x + N; i++) {
			for (int j = y; j < y + N; j++) {
				if (color != paper[i][j]) {
					find(x, y, N / 2);
					find(x, y + N / 2, N / 2);
					find(x + N / 2, y, N / 2);
					find(x + N / 2, y + N / 2, N / 2);
					return;
				}
			}
		}

각 사분면에 들어있는 값을 비교하는데 만약  color와 다르면 나누기를 진행한다.

여기서 color와 다르다는 것은 완전한 색상의 N*N 사각형을 이루지 않는다와 같은 뜻이다.

 

		if(color == 0) cnt0++;
		else cnt1++;

나누는 작업을 진행하지 않았으면 온전한 N*N행렬로 만약 color가 0이면 result에 0을 넣고 color가 1이면 result에 1을 넣는다.

 

		System.out.println(cnt0);
		System.out.println(cnt1);

각 색상을 가지는 색종이가 몇개 인지 확인하여 출력해준다.