백준_1780 종이의 개수(자바) / 재귀

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_1780 {

	static int N;
	static int[][] arr;
	static int[] ans= new int[3];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		StringTokenizer st;
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		
		divide(0,0,N);
		System.out.println(ans[0]);
		System.out.println(ans[1]);
		System.out.println(ans[2]);
	}
	private static void divide(int x, int y, int n) {
		if(check(x,y,n)) {
			ans[arr[x][y]+1]++;
		}else {
			int tmp = n/3;
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					divide(x+tmp*i, y+tmp*j, tmp);
				}
			}
		}
	}
	private static boolean check(int x, int y, int n) {
		int tmp = arr[x][y];
		for (int i = x; i < n+x; i++) {
			for (int j = y; j < y+n; j++) {
				if(tmp != arr[i][j]) {
					return false;
				}
			}
		}
		return true;
	}
}

 

- 이 문제는 분할 및 체크를 하면서 푸는 재귀 문제입니다.

- 전체의 크기에서 9분할을 진행해줍니다.

- 각 분할된 부분에서 모두 동일한 숫자가 들어왔는지 확인을 해줍니다.

- 모두 동일하다면 결과 처리를 해주고, 같지 않다면 그 부분에 대한 9분할을 다시 반복해줍니다.