[JAVA 자바] 백준 2630번 : 색종이 만들기

▶ 문제

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

2630번: 색종이 만들기

▶ 설명

단계별 문제 풀기에서 분할정복 카테고리에 있는 첫 문제인 색종이 만들기를 풀어보았다.

전체 상태에서 해결할 수 없을 때 분할하여 해결하는 방식을 분할 정복이라고 한다.

그래서 이 문제도 하나의 종이에서 같은 색이 아닐 경우 4등분으로 분할하여 같은 색으로 되어있는지 재귀함수로 체크하는 방식으로 색의 개수를 늘려나갔고 검색이 끝나면 흰색과 파란색 종이의 개수를 반환하도록 하였다.

 

먼저 colors 배열을 반들고 그 안에 0과 1로 되어 있는 입력값들을 저장하였다.

그럼 이 배열을 가지고 분할된 변의 길이 범위 안에서 같은 색으로 되어 있는지를 판단할 수 있게 된다.

그 판단을 findCnt()메소드에서 처리하도록 하였다.

 

findCnt()메소드 내용.

1. 설정한 사이즈 안의 색종이들이 같은 색인지 체크한다. 
2. 같은 색이면 그 색으로 cnt 증가. or  다른 색이 섞여 있으면 다시 4등분 (재귀) 한다.

 

코드로 풀어보면 아래와 같다.

 

▶ 문제 풀이

🌱 풀이.  

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

public class Main {

	static int[][] colors; // 입력된 색의 배열

	static int whiteCnt = 0; // 흰색 종이 개수
	static int blueCnt = 0; // 파란 종이 개수

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

		int n = Integer.parseInt(br.readLine()); // 전체 종이의 한 변의 길이
		colors = new int[n][n];

		// colors 배열에 입력된 색의 값 넣기.
		for (int i = 0; i < colors.length; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < colors[i].length; j++) {
				colors[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		findCnt(0, 0, n); // 탐색을 시작하는 인덱스 [0,0]와 탐색하는 한 번의 길이
		System.out.println(whiteCnt + "\n" + blueCnt);
	}

	private static void findCnt(int x, int y, int size) {

		if (sameColor(x, y, size)) {
			if (colors[x][y] == 1) {
				blueCnt++;
			} else {
				whiteCnt++;
			}
		} else {
			// 한 변의 길이를 전체 길이에서 반으로 나누기
			int halfSize = size / 2;

			// 4등분 했을 때 탐색할 시작 인덱스 4가지
			int[] sx = { x, x, x + halfSize, x + halfSize }; // start x
			int[] sy = { y, y + halfSize, y, y + halfSize }; // start y

			// 4등분 했으므로 4번 반복
			for (int i = 0; i < 4; i++) {
				findCnt(sx[i], sy[i], halfSize);
			}
		}
	}

	private static boolean sameColor(int x, int y, int size) {
		// 한 변의 길이가 1일 때 무조건 하나의 색으로 되어 있으므로 true를 반환.
		if (size == 1) {
			return true;
		} else {
			int color = colors[x][y];

			for (int i = x; i < x + size; i++) {
				for (int j = y; j < y + size; j++) {
					if (colors[i][j] != color) {
						return false;
					}
				}
			}
			return true;
		}
	}

}

 

어떤 2차 배열 요소의 인덱스 값과 row, col 길이를 안다면 범위를 정확히 알 수 있어 원하는 만큼의 범위로 배열을 출력하거나 탐색할 수 있다. 

그래서 색의 개수를 구하는 findCnt메소드는 물론, 원하는 범위 안에서 같은 색끼리 뭉쳐 있는지를 판별할 수 있는 sameColor 메소드에서 인수로 인덱스와 row/col 값이 될 수 있는 변의 길이를 넣을 수 있었던 것이다.

 

메소드 sameColor

sameColor 메소드를 통해 모두 같은 값이면 true, 다른 값이 섞여 있으면 false를 반환하도록 하였다.

이 때  시작점인 colors[x][y]의 값을 기준으로 하여 첫번째 인덱스의 값과 다른 인덱스들을 비교하는 것이다.

비교했을 때 다른 값이 발견되면 false를 반환하고, 다른 값이 나오지 않은채로 검색이 마치면 다른 색이 없다는 뜻이므로 true를 반환하게 된다.

 

 

 

 

▶ Log

재귀함수는 여러번 호출이 되므로 연속성을 염두해 두어야 한다. 이전 작업에서 이어지면서 같은 일들을 반복하기 때문이다.

매개변수를 어떤 것으로 구성할지도 잘 고민해봐야 한다.

다행히도(?) 분할정복에선 구역을 나누어 같은 작업을 반복하는 것이므로 어떤 기능으로 구성해야 겠다라는 경계가 분명해 보여 메소드를 구성하는 것이 아주 어렵지만은 않았다. 하지만 어떻게 문제를 풀어서 결과에 도달할지에 대한 문제 전체적인 이해가 중요해 보인다.