백준 2630 - 색종이 만들기(자바 - 분할정복)

재귀 호출을 활용하는 분할 정복 알고리즘 숙지를 위해 풀어볼 문제를 찾던 중 맞닥뜨린 곤혹스러운 문제

 

색종이 문제는 퀵 정렬, 병합 정렬등 분할정복과 재귀가 활용되는 알고리즘을 익히고 관련문제를 풀면서 숙련도를 키우던 도중, 처음 마주쳤을 때 도대체 이걸 어떻게 풀어야 하나 하고 감이 안 잡히던 곤혹스러운 문제였다.

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

2630번: 색종이 만들기

 

쿼드 트리? 처음 들어보는데?

문제를 풀고 싶어도 도저히 감이 잡히지 않아 이 문제에 대해 알아본 결과 쿼드 트리 자료 구조를 활용해야 하는 문제라는 사실을 알아냈다.

- 여기서 쿼드 트리란, 트리에서 각 노드들이 자식 노드를 4개씩 가지고 있는 트리를 말한다.

 

쿼드 트리라는 자료구조가 사용되는 것을 알아낸건 좋았는데, 이 문제에 대해 다른 사람들이 블로그에 작성해놓은 코드를 조금씩 훑어봐도 쿼드 트리라는 개념을 코드로 구현했을 때 어떤 식으로 프로세스가 흘러가는지 잘 감이 잡히지 않았다.(그렇다고 다른 사람의 코드를 자세히 살펴보지는 않았다. 왠지 답안지를 훔쳐보는 기분이기도 하고, 결정적으로 다른 사람의 코드를 자세히 보고 참고하게 되면 받게될 패배감을 느끼기 싫었다.)

 

그렇게 고민을 거듭하던 도중 어느순간 문득 깨달음을 얻었다.

 

이 문제는 이런식으로 풀어보면 되지 않을까?

- 재귀 호출의 변수 입력값(파라미터)으로 색종이를 4분할 했을 때 각 분할된 색종이의 좌표에 대해 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래 인덱스에 해당하는 값을 준다.

- 처음 재귀 호출용 함수가 호출될 때 현재 데이터가 들어있는 2차원 배열에서, 입력값으로 들어온 사분면 좌표를 기준으로 (0,0) 좌표에 해당하는 값과, 범위내에 있는 값들을 비교하여 모든 값들이 일치하면 어떤색인지 판별 후 해당하는 색깔의 갯수를 1 증가시킨다.

- 그렇지 않으면 현재 사분면을 4분할 하여, 그에 해당 하는 각각의 좌표들을 각 사분면의 범위를 탐색할 재귀 함수에 입력값으로 준 후 계속해서 재귀 호출을 수행한다.

 

위와 같은 느낌으로 프로세스가 흘러가도록 작성하여 통과한 코드는 다음과 같다.

- Main.java

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


public class Main {
	
	private static int[][] confetti = null;
	private static int whiteCount = 0;
	private static int blueCount = 0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		confetti = new int[N][N];
		
		StringTokenizer st = null;
		for(int i = 0; i < confetti.length; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < confetti[i].length; j++) {
				confetti[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		divideAndConquer(0,N,0,N);
		
		bw.write(whiteCount + "\n");
		bw.write(blueCount + "\n");
		bw.flush();
		bw.close();
	}

	private static void divideAndConquer(int x1, int x2, int y1, int y2) {
		
		int standard = confetti[x1][y1];
		boolean colorCheck = true;
		
		for(int i = x1; i < x2; i++) {
			for(int j = y1; j < y2; j++) {
				if(standard != confetti[i][j]) {
					colorCheck = false;
					break;
				}
			}
				
			if(!colorCheck)
				break;
		}
		if(colorCheck) {
			if(standard == 0)
				whiteCount++;
			else
				blueCount++;
		}
		else {
			divideAndConquer(x1, (x1+x2)/2, y1, (y1+y2)/2);
			divideAndConquer(x1, (x1+x2)/2, (y1+y2)/2, y2);
			divideAndConquer((x1+x2)/2, x2, y1, (y1+y2)/2);
			divideAndConquer((x1+x2)/2, x2, (y1+y2)/2, y2);
		}	
	}
}