#2630 : 색종이 만들기

풀이방법

사용된 것:

분할 정복

재귀

 

2022.05.18

분할 정복 문제이고, 재귀적으로 정의된 함수를 사용한다.

 

사용한 전역변수는 다음과 같이 3개이다.

• boolean[][] paper : 종이 정보. 파란색인 부분은 true, 하얀색인 부분은 false로 저장한다.
• int answer_w : 첫 줄에 출력될 정답. 완성된 하얀 색종이의 개수를 저장한다.
• int answer_b : 둘째 줄에 출력될 정답. 완성된 파란 색종이의 개수를 저장한다.

 

먼저 종이 정보를 읽어오고,

answer_w와 answer_b를 0으로 초기화시키고,

함수 cut()을 수행하고,

answer_w와 answer_b를 출력하면 된다.

 

 

cut()의 구성은 다음과 같다.

 

함수 cut()

개요

cut()은 주어진 영역의 색이 통일되어있는지를 점검하여,

통일되어있다면 answer_w 또는 answer_h 중 하나를 1 증가시키고

통일되어있지 않다면 영역을 4개로 쪼개어 이 4개 부분 영역에 대하여 재귀적으로 cut()을 실행하는 함수이다.

 

매개변수

• int startrow : cut()에서 점검할 영역의 시작부분(가장 왼쪽 위 지점)의 열 좌표
• int startcol : cut()에서 점검할 영역의 시작부분(가장 왼쪽 위 지점)의 행 좌표
• int len : cut()에서 점검할 영역의 한 변의 길이

 

작동방식

주어진 영역의 첫 칸(가장 왼쪽 위 지점)의 색을 boolean형 변수 first에 저장한다.

 

주어진 영역의 전체가 first와 색이 같은지 점검한다. 그 점검법은 다음과 같다.

1. boolean형 변수 check를 선언하고 true로 초기화한다.
2. 2중 for문을 사용하여 영역의 모든 칸을 점검한다. 그러다가 first와 색이 다른 칸이 발견되는 순간! check를 false로 바꾸고 2중 for문을 종료한다. first와 색이 다른 칸이 하나도 없다면 2중 for문은 중단되지 않은 채 끝나고 check는 true로 남아있게 된다.

check가 false라면,

영역을 4개로 쪼갠 후 그 4개의 영역에 대하여 재귀적으로 cut을 수행한다.

 

check가 true라면,

first가 true일 경우 answer_b의 값을 1 증가시킨다.

first가 false일 경우 answer_w의 값을 1 증가시킨다.

 

 

코드

Java(2022.05.18)

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

public class Main {
	
	static boolean[][] paper;	//종이
	static int answer_w;	//하얀 색종이의 개수
	static int answer_b;	//파란 색종이의 개수
	
	//특정 영역을 점검하여, 한 색상으로 통일되어있지 않으면 자르는 함수
	public static void cut(int startrow, int startcol, int len) {
		//startrow와 startcol는 영역의 가장 왼쪽 위 부분의 좌표
		//len은 영역의 한 변의 길이
		
		boolean first = paper[startrow][startcol];	//가장 왼쪽 위 부분의 색
		boolean check = true;	//점검결과가 저장될 boolean 변수
		
		//영역의 모든 부분이 first와 동일한지 점검
		for(int i = startrow; i<startrow+len; i++) {
			for(int j = startcol; j<startcol+len; j++) {
				if(paper[i][j]!=first) {check = false; break;}
			}
		}
		
		//색이 통일되어있지 않다면 자르기
		if(!check) {
			//네 부분의 시작위치 지정
			int[] r = {0, 0, len/2, len/2};
			int[] c = {0, len/2, 0, len/2};
			//네 부분에 대하여 재귀적으로 cut 수행
			for(int i = 0; i<4; i++) {
				cut(startrow+r[i], startcol+c[i], len/2);
			}
		}
		//색이 통일되어있다면 정답에 반영하기
		else {
			if(first) answer_b++;
			else answer_w++;
		}
		return;
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//입력값 읽어오기
		int n = Integer.parseInt(br.readLine());
		paper = new boolean[n][n];
		for(int i = 0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j= 0; j<n; j++) {
				if(st.nextToken().equals("1")) paper[i][j]=true;
				else paper[i][j] = false;
			}
		}
		
		//변수 초기화
		answer_w = 0;
		answer_b = 0;
		//자르기
		cut(0, 0, n);
		//정답 출력
		System.out.println(answer_w);
		System.out.println(answer_b);

	}

}