#1780 : 종이의 개수

풀이방법

사용된 것:

분할 정복

재귀

 

2022.05.28

백준 2630번 색종이 만들기 문제와 매우 유사하다. 색이 2가지에서 3가지로 증가하였다는 점, 그리고 분할하는 영역의 개수가 4개에서 9개로 증가하였다는 점 이렇게 딱 두 가지만 달라졌다.

#2630 : 색종이 만들기

 

 

코드

언어(2000.05.04)

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

public class Main {
	
	static int[][] paper;	//종이
	static int[] answer;	//정답을 저장할 배열
	
	//특정 영역을 점검하는 분할정복 함수
	static void solve(int row, int col, int len) {
		//row와 col은 시작 지점의 좌표, len은 영역의 한 변의 길이
		
		//먼저 해당 영역의 수들이 모두 일치하는지 점검
		boolean check = true;
		int first = paper[row][col];
		for(int i=row; i<row+len; i++) {
			for(int j=col; j<col+len; j++) {
				if(paper[i][j] != first) {
					check = false;
					break;
				}
			}
		}
		//영역의 수들이 모두 일치할 경우 정답을 업데이트
		if(check) answer[first+1]++;
		//값이 다른 수가 하나라도 있을 경우 9개 영역으로 분할하여 재귀
		else {
			int nextLen = len/3;
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) solve(row+(i*nextLen), col+(j*nextLen), nextLen);
			}
		}
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		paper = new int[n][n];
		answer = new int[3];
		//종이 정보 읽어오기
		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());
			}
		}
		//분할정복 하기
		solve(0, 0, n);
		//정답 출력하기
		for(int i:answer) {
			System.out.println(i);
		}
	}

}