/ BOJ

BOJ_1780_종이의개수_JAVA

문제 : 종이의 개수

링크 : BOJ_1780_종이의 개수

접근 방식

앞서서 풀었던 문제인 색종이 만들기와 판박이인 문제였다. 다른 점은 4분할이 9분할로 바뀌었고, 구분하는 구분자가 3개가 된 것, 그 부분 이외에는 분할정복으로 푸는 같은 문제라고 생각해도 된다. 배열이 모두 같은 수로 이루어질 때까지 9분할 시키고, 모든 배열이 같은 수로 이루어졌을 때, 사각형의 개수를 출력하면 된다.

풀이 방법

  1. 먼저 배열의 크기를 읽어와 변수 N에 저장하고, N*N크기의 배열을 생성해 배열에 입력값을 할당한다.

  2. 분할정복 알고리즘을 적용한다. 메서드의 인자값으로는 x,y 좌표값 그리고 배열의 크기 N을 받는다.

  3. 개수를 카운트할 변수를 하나 생성하고, 배열을 탐색하며 배열의 모든 수를 카운트 변수에 더한다.

  4. 4분할이 아니고, 구분하는 수도 -1,0,1 세 가지이기 때문에 배열 내부의 값을 더하는 것으로는 모두 같은 수로 이루어졌는지 확인할 수 없다. 따라서 첫 번째 좌표의 값을 저장해두고, 배열을 탐색하여 배열의 모든 값이 첫번째 좌표의 값과 같으면 모두 같은 수로 이루어진 배열로 판단한다. 만약 위 상황에 위반되는 경우, 같은 수로 이루어진 사각형이 아니므로, 배열을 9분할 시켜서 재귀호출한다.

  5. -1,0,1의 사각형의 갯수를 각각 더하여 순서대로 출력해준다.

소스 코드


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

public class BOJ_1780_종이의개수 {
	static int N, arr[][], cnt[] = new int[3];
	public static void main(String[] args) throws NumberFormatException, IOException {


		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());

		arr = new int[N][N];
		StringTokenizer st;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j=0;j<N;j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		d(0,0,N);		

		for(int i=0;i<3;i++) {
			System.out.println(cnt[i]);
		}
	}

	public static void d(int x, int y,int N) {
		int num = arr[x][y];
		boolean check = false;
		for(int i=x;i<x+N;i++) {
			for(int j=y;j<y+N;j++) {
				if(arr[i][j] != num) {
					check = true;
				}
			}
		}
		if(!check) {
			cnt[num+1]++;
			return;
		}

		int div = N/3;
		// 1분면
		d(x,y,div);
		// 2분면
		d(x,y+div,div);
		// 3분면
		d(x,y+div*2,div);

		// 4분면
		d(x+div,y,div);
		// 5분면
		d(x+div,y+div,div);
		// 6분면
		d(x+div,y+div*2,div);

		// 7분면
		d(x+div*2,y,div);
		// 8분면
		d(x+div*2,y+div,div);
		// 9분면
		d(x+div*2,y+div*2,div);

	}

}