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

 
www.acmicpc.net/problem/2630

2630번: 색종이 만들기

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

분할 정복의 첫 문제다.

 

원리만 이해한다면 그리 어렵진 않으니 차근차근 살펴보도록 하자.

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

여러분이 분할 정복 문제를 풀기 전에 기본적으로 알고있어야 할 지식이 있다.

 

1. 재귀에 대한 이해

2. 탐색(search)에 대한 이해

 

위 두 개의 기본 이해를 바탕으로 분할 정복을 풀이할 수 있다.

 

 

기본적으로, 분할 정복의 과정은 3단계로 나뉜다.

 

1. 현재 상태의 문제를 풀 수 없는 경우 문제를 분할 할 수 있는지를 확인한다.

2. 문제를 분할하여 각각 풀이한다. (풀이 할 수 없는 경우 1번 과정으로 간다.)

3. 풀린 문제들을 합친다.

 

 

위 세 가지 과정이 기본 토대가 된다.

 

 

사실 분할 정복 문제를 생소하게 생각 할 수도 있지만 여러분이 이미 카테고리대로 진행했다면 몇 개의 분할 정복 문제를 풀어봤었을 것이다.

대표적으로, '별찍기 10' 문제가 있다.

 

st-lab.tistory.com/95

[백준] 2447번 : 별 찍기 - 10 - JAVA [자바]

 

이 문제를 풀어보셨다면 알겠지만, 전체 보드(board)에서 공백 부분이 아닐 경우 1/3 씩 쪼개서 서브(부분) 문제로 재귀호출 하면서 풀었다.

 

이러한 과정과 이 번 색종이 문제 또한 매우매우 유사하게 풀이 할 수 있다.

 

 

 

그럼 색종이 만들기 예제를 갖고 한 번 어떻게 풀어야 하는지, 그 접근 방법을 알아보도록 하자.

일단, 흰색과 파란색 정사각형 색종이의 개수를 알아내야 하는데, 규칙은 이렇다.

 

부분 색종이는 모두 같은 색상이어야 한다.

만약 모두 같은 색상이 아닐 경우 색종이를 잘라야 한다.

색종이를 자를 때는 1/2 씩, 즉 절반씩 잘라서 정사각형을 얻어야 한다. 

 

 

즉, 전체적인 과정은 다음과 같다.

 

 

즉, 전체적인 알고리즘을 구상하자면 다음과 같은 과정으로 짤 수 있다.

 

 

 

main :
	partition(0, 0, N);

func partition(int row, int col, int size) :

	/*
	 * 만약 현재 파티션(부분)이 모두 같은 색상이라면
	 * 현재 색상을 1 증가시키고 함수 종료
	 */
	if colorCheck is True :
		if color is white(0) :
			white = white + 1
		else :
			blue = blue + 1;
		return;

	size = size / 2;	// 사이즈를 절반으로 줄인다.

	partition(row, col, size);					// 분할 된 2사분면
	partition(row, col + size, size);			// 분할 된 1사분면
	partition(row + size, col, size);			// 분할 된 3사분면
	partition(row + size, col + size, size);	// 분할 된 4사분면

 

 

1. 각각의 행과 열의 시작점(초기는 (0, 0)이 기준)에서 현재 파티션에 대하여 모두 같은 색상인지 체크를 먼저 해야한다.

2. 색상이 같다면 해당 색상의 개수를 1 증가시키고 함수를 종료한다.

3. 색상이 같지 않다면, 4등분 하여 각 부분 문제로 쪼개어 문제를 푼다.

 

 

위 3가지 과정과 색상이 같은지를 알아 내기 위한 함수를 코드로 작성하면 된다. 자세한 코드는 아래 풀이에서 보도록 하자.

 

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

 

그동안의 다른 포스팅과 다를 거 없이 두 가지 입력 방법을 통해 성능을 비교해보려 한다. 알고리즘은 위 과정을 그대로 갖고와 작성 할 것이다.

 

1. Scanner

2. BufferedReader

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;


public class Main {
	
	// 색상 카운트 할 변수 및 색종이(board)
	public static int white = 0;
	public static int blue = 0;
	public static int[][] board;

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		board = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				board[i][j] = in.nextInt();
			}
		}
		
		partition(0, 0, N);
		
		System.out.println(white);
		System.out.println(blue);
		
	}
	
	public static void partition(int row, int col, int size) {
		
		//
		if(colorCheck(row, col, size)) {
			if(board[row][col] == 0) {
				white++;
			}
			else {
				blue++;
			}
			return;
		}
		
		int newSize = size / 2;	// 절반 사이즈
		// 재귀 호출
		partition(row, col, newSize);						// 2사분면
		partition(row, col + newSize, newSize);				// 1사분면
		partition(row + newSize, col, newSize);				// 3사분면
		partition(row + newSize, col + newSize, newSize);	// 4사분면
	}
	
	
	// 현재 파티션의 컬러가 같은지 체크한다.
	public static boolean colorCheck(int row, int col, int size) {
	
		int color = board[row][col];	// 첫 번째 원소를 기준으로 검사
		
		for(int i = row; i < row + size; i++) {
			for(int j = col; j < col + size; j++) {
				// 색상이 같이 않다면 false를 리턴 
				if(board[i][j] != color) {
					return false;
				}
			}
		}
		// 검사가 모두 통과했다는 의미이므로 true 리턴
		return true;
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

문제 자체도 그리 어렵진 않아서 금방 풀었을 것이다.

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 공백을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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


public class Main {
	
	// 색상 카운트 할 변수 및 색종이(board)
	public static int white = 0;
	public static int blue = 0;
	public static int[][] board;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		board = new int[N][N];
		
		StringTokenizer st;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			for(int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		partition(0, 0, N);
		
		System.out.println(white);
		System.out.println(blue);
		
	}
	
	public static void partition(int row, int col, int size) {
		
		//
		if(colorCheck(row, col, size)) {
			if(board[row][col] == 0) {
				white++;
			}
			else {
				blue++;
			}
			return;
		}
		
		int newSize = size / 2;	// 절반 사이즈
		// 재귀 호출
		partition(row, col, newSize);						// 2사분면
		partition(row, col + newSize, newSize);				// 1사분면
		partition(row + newSize, col, newSize);				// 3사분면
		partition(row + newSize, col + newSize, newSize);	// 4사분면
	}
	
	
	// 현재 파티션의 컬러가 같은지 체크한다.
	public static boolean colorCheck(int row, int col, int size) {
	
		int color = board[row][col];	// 첫 번째 원소를 기준으로 검사
		
		for(int i = row; i < row + size; i++) {
			for(int j = col; j < col + size; j++) {
				// 색상이 같이 않다면 false를 리턴 
				if(board[i][j] != color) {
					return false;
				}
			}
		}
		// 검사가 모두 통과했다는 의미이므로 true 리턴
		return true;
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 27399399  -  방법 2 : BufferedReader

채점 번호 : 27399392  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이 번 문제는 재귀에 대한 기본 지식이 있다면 그리 어렵지 않게 풀었을 것이다.

분할 정복의 경우 위 처럼 문제를 병렬적으로 처리하는데 장점이 있고, 큰 문제를 작은 문제를 쪼개면서 들어가기 때문에 풀린 문제의 경우 더이상 탐색하지 않아도 된다.

 

하지만 반대로 재귀호출로 구현하게 될 경우 오버헤드가 발생한다는 단점 또한 존재한다. 

물론 재귀 호출 방식이 아니라 스택, 큐 같은 자료구조를 활용하여 구현하기도 한다.

 

특히 이후 병합정렬이나 퀵 정렬을 구현 할 때 분할 정복 방식이 활용되기 때문에 분할 정복 알고리즘에 대해 정확한 이해를 갖고 있는 것을 추천드린다.

 

만약 어렵거나 모르는 부분이 있다면 언제든 댓글 남겨주시길 바란다 :)