[Silver2-JAVA] 백준 1780 - 종이의 개수

https://www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

 

🤔 문제 풀이

쉽지 않았던 분할 정복 문제였다.

처음 문제를 풀었을 때 계속된 재귀호출을 통해 종이들을 분할하여

풀어나가는 방법임은 짐작했으나 종이들을 나누는 과정을 생각해내는 것이

무척 어려웠다. 

 

첫 종이의 전체 요소들이 전부 같은지 검사하고

만약 다르다면 row/3 col/3 하여 9칸으로 나누고 나뉜 종이들을

다시 검사하고... 이런 과정의 반복이었다.

 

종이들을 분할하기 위해 필요한 것은 각 종이들의 시작 좌표 start 와 전체 size이다.

첫 종이를 제외한 각각의 종이들은 start 좌표에서 size/3 (div)의 범위를 검사해주면된다.

map[start + size * n][start + size * m], 이때 n,m은 0~2

🚨CODE

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Main {
	static int[][] map;
	static int[] answer;
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		map = new int[n+1][n+1];
		answer = new int[3]; // 0 => 0, 1 => 1, 2 => -1
		
		for(int i = 1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j<=n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		search(1, 1, n);
		System.out.println(answer[2]);
		System.out.println(answer[0]);
		System.out.println(answer[1]);
	}
	public static void search(int row, int col, int size) {
		if(check(row, col, size)) {
			if(map[row][col] == -1) {
				answer[2] ++;
			}else if(map[row][col] == 0) {
				answer[0] ++;
			}else {
				answer[1] ++;
			}
			return;
		}
		
		int div = size/3;
		
		search(row, col, div);
		search(row, col+div, div);
		search(row, col+div*2, div);
		
		search(row+div, col, div);
		search(row+div, col+div, div);
		search(row+div, col+div*2, div);
		
		search(row+div*2, col, div);
		search(row+div*2, col+div, div);
		search(row+div*2, col+div*2, div);
		
	}
	public static boolean check(int row, int col, int size) {
		int element = map[row][col];
		
		for(int i = row; i<row+size; i++) {
			for(int j = col; j<col+size; j++) {
				if(map[i][j] != element)
					return false;
			}
		}
		return true;
	}
}