[백준/분할정복] 2630: 색종이 만들기 - 자바

문제

---

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

2630번: 색종이 만들기

 

풀이

---

분할정복 문제를 많이 풀어보지 않아 꽤 어려워 솔루션을 참고한 문제..

핵심은 전체 N크기를 2등분씩 하면서 1,2,3,4 분면씩 나누어 분할 탐색하는 것이 포인트

 

처음에 해당 사분면의 r,c 값과 r+size, c+size까지 돌면서 흰색인지, 파란색인지 체크하면된다.

만약 size크기만큼 탐색하면서 처음 temp에 넣었던 값과 다른값이 나온다면

boolean자료형인 check에 false를 주어서 해당 size만큼의 색종이 크기가 완전히 나누어 지지 않았음을 체크하였음

false일 때 size /=2 를 하여 1,2,3,4 분면을 다시 탐색함.

 

만약 해당 size크기만큼 배열을 탐색하여 온전한 색종이라고 판단되었을 때에는 cnt값을 증가시킴

백준에 이와 비슷한 Z 문제 도 이런식으로 접근하면 될 것같다.

코드는 다음과 같이 작성하였다.

 

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

public class BOJ_2630 {
	static int N;
	static int[][] map;
	static int[] cnt;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		cnt = new int[2];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j]= Integer.parseInt(st.nextToken());
			}
		}
		solution(0, 0, N);
		System.out.println(cnt[0]);
		System.out.println(cnt[1]);
	}
	public static void solution(int r, int c, int size) {
		int temp = map[r][c];
		boolean check = true;
		for(int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				if(temp != map[i][j]) {
					check = false;
					break;
				}
			}
		}
		
		if(check) cnt[temp]++;
		
		else {
			size /= 2;
			solution(r, c, size);
			solution(r+size, c, size);
			solution(r, c+size, size);
			solution(r+size, c+size, size);
		}
	}
}

메모리: 13020 KB
실행시간: 112 ms
코드길이: 1133 B