[BAEKJOON] 2630 색종이 만들기 - JAVA

문제 요약

• 알고리즘 분류: 분할정복, 재귀호출
• 난이도: Silver2
• 문제내용:
  • 종이안에 정사각형 흰색 영역 개수와 파란색 영역을 구해라.

• 사이트: https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

문제풀이

   이번에는 문제 유형은 완전탐색 방법에서 분할 정복으로 풀어야 될 문제이다. 어떻게 분할해서 풀면 된다.  나누는 방법은 간단하다. 문제에서는 주어진 가로세로 길이가 2^N이기 때문에 가로세로 각각 2로 나누어서 탐색 한 영역서 나누는 경의수가 4가지이다. 현재 가로, 세로 위치를 x, y라고 하고 한변의 길이가 N 이라고 가정하자.

1. (x, y, n / 2)
2. (x + n / 2, y , n / 2)
3. x, y  + n/ 2, n / 2
4. x + n / 2, y + n / 2, n / 2

위 4가지 경우를 탐색해서 만약에 그 영역안에서 색이 다 같으면 흰색 또는 파란색 개수에 추가 하고 아니면 또 4가지경우수로 분할 해서 탐색해서 찾아 내면 된다.

Code

Java

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

public class Main {
	
	static int white = 0;
	static int blue = 0;
	static int[][] paper;
	
	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];
		StringTokenizer st;
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				paper[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		divied(0, 0, N);
		System.out.println(white);
		System.out.println(blue);
	}
	
	public static void divied(int x, int y, int n) {
		boolean flag = true;
		// 색종이 통일 되어 있는지 탐색
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				// 다른 색 하나 있을 경우
				if(paper[x][y] != paper[x + i][y + j]) {
					flag = false;
					break;
				}
				if(!flag) break;
			}
		}
		// 탐색한 영역이 한가지 색으로 통일된 경우
		if (flag) {
			if(paper[x][y] == 0) {
				white++;
			}else {
				blue++;
			}
		}else {
			divied(x, y, n / 2);
			divied(x + n / 2, y, n / 2);
			divied(x, y + n / 2, n / 2);
			divied(x + n / 2, y + n / 2, n / 2);
		}
	}
	
}