백준 1780 - 종이의 개수

[문제 바로가기]

 

1. 유형

분할 정복

 

2. 접근법

2-1. 해설

분할 정복으로 푸는 문제 입니다.

전체 사각형을 기준으로 잡고, 세부 사각형이 모두 같은지 판단해 줍니다.

그림1

[그림1]과 같은 사각형이 있다고 가정하겠습니다. 길이가 3일 때, 모두 같은지를 판단 합니다.

0과 1이 같이 있으니 분할 정복을 시도합니다.

 

 

위의 코드를 따르면 [그림2] 처럼 나올겁니다.

그림 2

이제 위의 코드를 계속 반복하면 끝!

 

2-2. 설계

전체가 같은 값 일 수 있으니 체크 -> DFS(큰변, 작은변, 좌표)를 호출 -> 작은 사각형이 동일 한지 여부에 따라 종이의 수 증가.

 

3. 코드

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

public class Main {
	static int N, grid[][], save[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		grid = new int[N][N];
		save = new int[3];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				grid[i][j] = stoi(st.nextToken());
			}
		}
		if(possible(N, 0, 0)) {
			int target = grid[0][0];
			save[target+1] ++;
		}else
			dfs(N, N/3, 0, 0);
		for(int k: save) {
			System.out.println(k);
		}
	}
	static void dfs(int large_len, int small_len, int r, int c) {
		
		for(int i=0; i<large_len; i+=small_len) {
			for(int j=0; j<large_len; j+=small_len) {
				if(possible(small_len, r+i, c+j)) {
					int target = grid[r+i][c+j];
					save[target+1]++;
				}else {
					dfs(small_len, small_len/3, r+i, c+j);
				}
			}
		}
	}
	static boolean possible(int len, int r, int c) {
		int target = grid[r][c];
		for(int i=0; i<len; i++) {
			for(int j=0; j<len; j++) {
				if(target != grid[i+r][j+c]) {
					return false;
				}
			}
		}
		return true;
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}