백준 2630 : 색종이 만들기

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

 

이번 문제는 백준 2630 색종이 만들기 문제이다.

카테고리는 분할 정복으로 되어 있지만, 결국 접근해야할 문제 방법은 재귀다.

재귀를 이용해서 색종이의 색이 일치하는지 안하는지를 확인해나가며 체크한다면 정답을 얻을 수 있다.

 

시간 체크를 안하기도 했지만, 단번에 풀어 큰 문제가 없다고 판단했다.^^

 

구해야할 것

흰 색종이와 푸른 색종이의 갯수

방법

1. 좌측 상단의 색종이 좌표와 우측 하단의 좌표를 구해 해당 색종이가 같은 색인지 확인한다.

2. 만약 색종이의 색이 같다면 좌측 상단의 색을 구하고 해당 색을 더해준다,

3. 색종이의 색이 같지 않다면 좌측 상단의 좌표와 우측 하단의 좌표를 이용해 색종이를 4개로 쪼갠다.

이때 좌표는 좌측상단 좌표와 우측 하단의 좌표를 이용해서 재귀식에 넣어준다.

 

아래는 코드 전문이다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Stream;

public class Main {
	private static int N, white, blue;
	private static int[][] colorPaper;

//	같은 색인지 확인
	public static boolean checkSameColor(Point LU, Point RD) {
		int initColor = colorPaper[LU.x][LU.y];
		for (int row = LU.x; row < RD.x; row++) {
			for (int col = LU.y; col < RD.y; col++) {
				if (initColor != colorPaper[row][col])
					return false;
			}
		}
		return true;
	}

//	checkSameColor 후 같지 않으면 자른다.
	public static void recursive(Point LU, Point RD) {
		if (checkSameColor(LU, RD)) {
//			System.out.println(LU.x + " " + LU.y + " " + RD.x + " " + RD.y);
			if (colorPaper[LU.x][LU.y] == 0) {
				white++;
			} else if (colorPaper[LU.x][LU.y] == 1) {
				blue++;
			}
			return;
		}
		recursive(LU, new Point((LU.x + RD.x) / 2, (LU.y + RD.y) / 2));
		recursive(new Point(LU.x, (LU.y + RD.y) / 2), new Point((LU.x + RD.x) / 2, RD.y));
		recursive(new Point((LU.x + RD.x) / 2, LU.y), new Point(RD.x, (LU.y + RD.y) / 2));
		recursive(new Point((LU.x + RD.x) / 2, (LU.y + RD.y) / 2), RD);
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		colorPaper = new int[N][N];

		for (int i = 0; i < N; i++) {
			colorPaper[i] = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		}

		white = 0;
		blue = 0;
		recursive(new Point(0, 0), new Point(N, N));

		System.out.println(white);
		System.out.println(blue);
	}
}