[BJ2630] 색종이 만들기

 SW Expert Academy - 숫자 카드 게임 

문제 링크

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

2630번: 색종이 만들기

 

문제 입출력

4
1 0 1 1
1 1 1 1
0 0 0 0
0 0 1 1

4
6

 

문제 풀이

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


public class Main {
	static int ansW, ansB, N;
	static int[][] map;


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];

		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());
		}

		// 풀이
		go(0, N, 0, N);

		// 출력
		System.out.println(ansW);
		System.out.println(ansB);

	} // end main


	// (sy - ey), (sx - ex) 색종이가 다 같은 색으로 칠해져있는지 확인하고
	// 그렇지 않으면 나누는 함수
	private static void go(int sy, int ey, int sx, int ex) {
		// 기저조건: 만약 종이의 너비가 1이라면 return
		if (ey - sy < 1 || ex - sx < 1) return;

		if (!check(sy, ey, sx, ex)) {
			// 만약 전체가 다 같은 색으로 칠해져 있지 않다면
			// 4등분하여 재귀를 탄다. -> 또 다 같은 색으로 칠해져있는지 확인
			go(sy, (sy + ey) / 2, sx, (sx + ex) / 2);
			go(sy, (sy + ey) / 2, (sx + ex) / 2, ex);
			go((sy + ey) / 2, ey, sx, (sx + ex) / 2);
			go((sy + ey) / 2, ey, (sx + ex) / 2, ex);
		} else {
			// 만약 전체가 다 같은 색으로 칠해져 있다면
			// 첫번째 원소를 확인하여 흰색인지/파란색인지 센다.
			if (map[sy][sx] == 0) ansW++;
			else ansB++;
		}

	} // end solution


	private static boolean check(int sy, int ey, int sx, int ex) {
		int prev = map[sy][sx];

		for (int i = sy; i < ey; i++) {
			for (int j = sx; j < ex; j++) {
				if (prev != map[i][j]) return false;
				else prev = map[i][j];
			}

		}

		return true;
	} // end check

}

 

 

 

 

 

 

 

 

 

 

#백준 색종이만들기 java #백준 색종이 만들기 java

---