[Algorithm / Java] 백준 2630번 색종이 만들기

key word : 재귀, 쿼드 트리, 분할 정복

문제

색종이가 같은 색으로 칠해져있는지 확인한 후, 그렇지 않다면 색종이를 4분할 해가면서 같은 색으로만 칠해져있는 경우를 찾는다. 그 후 각 색깔의 종이가 몇 개인지 세는 문제이다.

아이디어

전체를 돌면서 같은 색인지 확인한 뒤, 아니라면 종이를 사분할해서 같은 작업을 반복하면 되는 쉬운 문제이다.

재귀로 풀 수 있으며 재귀 함수 내의 로직이 매우 간단하여 분할해서 넘겨주는 작업만 잘 하면 될 것 같았다. 그나마 주의할 점이라면 for문 내의 i의 값을 시작하는 배열의 위치로 초기화하고, 초기화값 + 돌아야하는 범위까지만 돌게끔 해줘야한다는 점이다. 습관적으로 i = 0 으로 썼다가 고쳤다.

아이디어 자체가 단순하므로 바로 구현에 들어갔다.

구현

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

public class ColorPaper {
	static int N;
	static int[][] paper;
	static int blue = 0, white = 0;

	public static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		paper = new int[N][N];

		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				paper[i][j] = Integer.parseInt(st.nextToken());
			}
		}
	}

	public static void recursion(int n, int r, int c) {
		if(n == 1) {
			if(paper[r][c] == 1) {
				blue++;
			}else {
				white++;
			}
			return;
		}

		int color = paper[r][c];
		for(int i=r; i<r + n; i++) {
			for(int j=c; j<c + n; j++) {
				if(paper[i][j] != color) {
					int half = n / 2;
					recursion(half, r, c);
					recursion(half, r, c + half);
					recursion(half, r + half, c);
					recursion(half, r + half, c + half);
					return;
				}
			}
		}
		if(color == 1) {
			blue++;
		}else {
			white++;
		}
	}

	public static void main(String[] args) throws IOException{
		init();
		recursion(N, 0, 0);
		System.out.println(white);
		System.out.println(blue);
	}

}