[백준] 2630. 색종이 만들기 (자바 JAVA)

[ 문제 ]  [백준] 2630. 색종이 만들기 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

---

# 접근 방법 및 풀이 

 

• 백준 "1992 쿼드트리"와 똑같은 문제라고 볼 수 있다. 요구하는 답이 다를 뿐.
• 쿼드 트리는 분할정복+재귀로 풀었다면, 이 문제는 그냥 재귀로 풀었다.
• 이 문제가 / 2 씩해서 종이를 나누어 가면, 백준 1780 종이를  / 3 으로 나누어갈 뿐 코드는 똑같다.
• 백준 1992. 쿼드트리 풀이: https://ilmiodiario.tistory.com/137
• 백준 1780. 종이의 개수 풀이: https://ilmiodiario.tistory.com/138
• 재귀문제 푸는 순서 추천방식은 "색종이만들기-> 쿼드트리 -> 종이의 개수"
• 자세한건 코드참조

# 주의할 점 

 

• 딱히 없음

 

JAVA 코드

package Silver;

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

public class bj2630_색종이만들기 {
	static int N, map[][], white = 0, blue = 0;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		solve(0, 0, N);
		System.out.println(white);
		System.out.println(blue);
	}
	private static void solve(int r, int c, int size) {
		if(check(r, c, size)) {
			if(map[r][c] == 0)
				white++;
			else
				blue++;
			return;
		}
		int newSize = size / 2;
		for (int i = r; i < r + size; i+=newSize) {
			for (int j = c; j < c + size; j+=newSize) {
				solve(i, j, newSize);
			}
		}
	}
	
	private static boolean check(int r, int c, int size) {
		for (int i = r; i < r + size; i++) {
			for (int j = c; j < c + size; j++) {
				if(map[r][c] != map[i][j])
					return false;
			}
		}
		return true;
	}
}

 

 

 

REVIEW