백준 1780 - 종이의 개수

Java

1780 번 - 종이의 개수

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

접근 방법

분할 정복의 기초적인 문제이다.
n x n 크기의 행렬을 전부 탐색하여 다 동일한 값이면 그 값의 개수를 1 증가하고,
하나라도 다르면, n/3 x n/3으로 총 9개로 나누어 각각 탐색한다.

구현

매개변수로 시작점 y,x와 탐색 할 크기 size를 전달하는 Paper 재귀 함수를 선언한다.
size가 1이면 해당하는 값의 개수를 1 증가한다.
탐색 시작점을 y,x로 두어 size만큼 행렬을 탐색하여 같으면 종료, 다르면 재 탐색한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, minus = 0, zero = 0, plus = 0;
	static int[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	arr = new int[n][n];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			arr[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
    	Paper(0,0,n);
    	System.out.println(minus);
    	System.out.println(zero);
    	System.out.println(plus);
    	br.close();
	}
	
	static void Paper(int y, int x, int size) {
		if(size == 1) {
			check(arr[y][x]);
			return;
		}
		// 기준 값
		int pivot = arr[y][x];
		boolean isSame = true;
		end : for(int i = y; i < size + y; i++) {
			for(int j = x; j < size + x; j++) {
				if(pivot != arr[i][j]) {
					isSame = false;
					break end;
				}
			}
		}
		// 모두 동일한 값일 때
		if(isSame)
			check(pivot);
		// n / 3 * n / 3으로 나누어 재 탐색한다.
		else {
			for(int i = 0; i < 3; i++) {
				for(int j = 0; j < 3; j++) {
					Paper(y + i * (size / 3), x + j * (size / 3), size / 3);
				}
			}
		}
	}
	static void check(int num) {
		switch(num) {
		case -1:
			minus++;
			break;
		case 0:
			zero++;
			break;
		case 1:
			plus++;
			break;
		}
	}
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

개선할 점

없