[Algorithm / Java] 백준 1780번 종이의 개수

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

문제

배열로된 종이에 모두 같은 숫자가 들어있는지 확인하는 문제이다. 다른 숫자가 들어있다면 종이를 9분할해서 또 같은 작업을 반복한다. 최종적으로 -1로만 채워진 종이, 0으로만 채워진 종이, +1로만 채워진 종이의 개수를 출력하면 된다.

직전에 풀었던 ‘색종이 만들기’문제와 매우 흡사하다. 백준에서 유형별 풀기로 재귀를 선택하고 만 명 안팎이 푼 문제들에 도전하다보니 유사한 문제를 연달아 풀게된 것 같다.

아이디어

이 문제도 어렵지 않게 풀 수 있었다. 배열을 돌며 같은 숫자인지 확인하고, 그렇지 않은 경우 재귀를 이용해 9분할한 종이에 대해 같은 작업을 반복했다. 단, 9분할하는 경우이므로 재귀함수를 호출할 때 인자를 잘 전달해야한다.

‘색종이 만들기’ 문제때와 달리 함수를 하나 더 만들어 사용했다. -1인지 0인지, 혹은 +1인지 확인하는 부분이 꽤 중복되는 것 같아 그걸 판별하고 알맞은 변수의 값을 올려주는 기능을 따로 빼줬다. 그런데 지금 다시 보니 base condition으로 둔 n = 1일 때를 따로 검사하지 않아도 정상적으로 동작하므로 그 부분을 빼는게 더 깔끔했을 것 같다.

구현

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

public class PaperCount {
	static int N;
	static int[][] paper;
	static int minus = 0, zero = 0, plus = 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());
			}
		}

		br.close();
	}

	public static void recursion(int n, int r, int c) {
		int num = paper[r][c];

		if(n == 1) {
			add(num);
			return;
		}

		int size = n / 3;
		for(int i=r; i<n + r; i++) {
			for(int j=c; j<n + c; j++) {
				if(paper[i][j] != num) {
					recursion(size, r, c);
					recursion(size, r, c + size);
					recursion(size, r, c + 2 * size);
					recursion(size, r + size, c);
					recursion(size, r + size, c + size);
					recursion(size, r + size, c + 2 * size);
					recursion(size, r + 2 * size, c);
					recursion(size, r + 2 * size, c + size);
					recursion(size, r + 2 * size, c + 2 * size);
					return;
				}
			}
		}

		add(num);
	}

	public static void add(int num) {
		if(num == -1) {
			minus++;
		}else if(num == 0) {
			zero++;
		}else {
			plus++;
		}
		return;
	}


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

}