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

문제 출처 : https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

 

 

문제

 

 

설명

백준의 Z, 쿼드 트리와 굉장히 유사한 유형의 이분탐색 문제입니다. 

사각형 안의 수가 다 동일하다면 white 또는 blue에 대한 수를 증가시켜 주고 재귀를 끝냅니다.

만약 동일하지 않다면, 재귀적으로 4등분하여 동일한 방법으로 살펴보는 것을 반복하는 식으로 구현했습니다.

맨 끝에 Z와 쿼드트리 코드 게시물도 링크 걸어 둘 테니, 필요하시다면 참고해 주세요 :) 

 

 

코드

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

public class BOJ2630_ColoredPaper {

	static int N;
	static int[][] square;
	static int white, blue;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		square = new int[N][N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				square[i][j] = Integer.parseInt(st.nextToken());
			}
		} //입력 완료
		
		solve(N, 0, 0);
		System.out.println(white);
		System.out.println(blue);
		
	}

	private static void solve(int n, int x, int y) {
		
		int sum=0;
		for(int i=x; i<x+n; i++) {
			for(int j=y; j<y+n; j++) {
				sum+=square[i][j];
			}
		}
		if(sum==0) { //구역이 전부 흰색인 경우
			white++;
		} else if(sum==n*n) { //구역이 전부 파란색인 경우
			blue++;
		} else { //섞여있는 경우 -> 4분할 필요
			int half = n/2;
			
			solve(half, x, y);
			solve(half, x, y+half);
			solve(half, x+half, y);
			solve(half, x+half, y+half);
			
		}
	}
}

 

 

- Z 문제 게시물 바로가기 👉 https://sutechblog.tistory.com/34?category=499410

[BOJ][JAVA] 1074 - Z

 

 

- 쿼드 트리 문제 게시물 바로가기 👉 https://sutechblog.tistory.com/41?category=499410 

[BOJ][JAVA] 1992 - 쿼드 트리