[백준] 단계별로 풀어보기(단계:20,분할 정복,JAVA)2630번, 색종이 만들기

문제 링크

2630번: 색종이 만들기

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

분할 정복 알고리즘은 일정한 간격으로 입력된 값을 분할하여 조건에 맞는지 확인하고 틀리면 다시 일정한 간격으로 분할하는 것을 반복하여 조건에 만족할 때까지 진행하는 알고리즘입니다.

 

조건에 맞는지 확인하고 일정한 간격으로 나눌 수 있도록 재귀를 사용하여 구현할 것입니다.

문제를 살펴보면 그림으로도 분할 정복이 이루어지고 있다는 것을 알려주고 있습니다.

해결 알고리즘을 살펴보면

1. 처음 종이가 색종이가 될 수 있는지 확인합니다.

2. 색종이가 되지 못한다면 4분할로 나눕니다.

3. 4분할로 나뉜 종이마다 색종이가 되는지 확인합니다.

4. 위 과정을 반복하여 파란색 색종이와 하얀색 색종이가 몇 개인지 결과로 출력합니다.

 

예제 입력을 살펴보면

1. 첫 종이가 색종이인지 확인을 합니다.

따로 표를 작성하지 않아도 1과 0이 섞여있으므로 색종이가 되지 않습니다.

2. 4분할하여 분할된 종이들이 색종이인지 확인합니다.

※(0, 0)을 기준으로 분할된 종이만 표로 작성하여 알고리즘이 어떻게 굴러가는지 알려드리겠습니다.

1	1	0	0
1	1	0	0
0	0	0	0
0	0	0	0

4분할로 나누었지만 1과 0이 섞여있으므로 색종이가 되지 못합니다.

3. 4분할로 나누었던 색종이를 다시 4분할로 나눕니다.

2사분면

1	1
1	1

1사분면

0	0
0	0

3사분면

0	0
0	0

4사분면

0	0
0	0

4분할된 모든 색종이가 동일한 값을 가지고 있으므로 2사분면은 파란색 색종이이고 나머지는 하얀색 색종이임을 알 수 있습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 종이의 값을 띄어쓰기 기준으로 나누어 배열에 저장하였습니다.
• 분할/색종이 확인/색종이 개수 더하기를 수행하는 confettiMake/paperCheck/countPlus 함수를 만들었습니다.
• 함수를 실행시켜 파란색/하얀색 색종이의 개수를 구하였습니다.
• BufferedWriter에 색종이의 개수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• confettiMake 함수는 위 알고리즘을 재귀를 통해 구현하였으며 색종이의 최소크기(1)이 되었을 때는 색종이로 인식하도록 하였습니다.
• paperCheck는 2중 for문을 사용하여 분할된 종이가 색종이인지 확인하도록 하였습니다.
• countPlus는 색종이에 색깔에 따라 개수를 증가시키도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int blue = 0, white = 0;	//색종이 개수 저장 변수
	static int[][] paper;	//입력되는 종이 값 배열
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 받는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //----------입력값 저장 및 배열 초기화---------
        int size = Integer.parseInt(br.readLine());
        paper = new int[size][size];
        StringTokenizer st;
        for(int i=0;i<size;i++) {
        	st = new StringTokenizer(br.readLine()," ");
        	for(int j=0;j<size;j++)
        		paper[i][j] = Integer.parseInt(st.nextToken());
        }
        confettiMake(0, 0, size);		//함수 실행
        bw.write(white + "\n" + blue + "\n");	//색종이 개수 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //----------종이 분할 및 색종이 구하는 함수---------
    public static void confettiMake(int start, int end, int size) {
    	int firstValue = paper[start][end];
    	if(size == 1) {
    		countPlus(firstValue);
    		return;
    	}
    	if(paperCheck(start, end, size, firstValue)) {
    		countPlus(firstValue);
    	}else {
    		int tempSize = size/2;
    		confettiMake(start, end, tempSize);	//2사분면
    		confettiMake(start, end + tempSize, tempSize);	//1사분면
    		confettiMake(start + tempSize, end, tempSize);	//3사분면
    		confettiMake(start + tempSize, end + tempSize, tempSize);	//4사분면
    	}
    	return;
    }
    //-----------색종이인지 확인 함수----------
    public static boolean paperCheck(int start, int end,
    		int size,int firstValue) {
    	int start_end = start + size;
    	int end_end = end + size;
    	for(int i=start;i<start_end;i++) {
    		for(int j=end;j<end_end;j++) {
    			if(paper[i][j]!=firstValue) {
    				return false;
    			}
    		}
    	}
    	return true;
    }
    //--------색종이 개수 더하는 함수--------
    public static void countPlus(int firstValue) {
		if(firstValue==1)
			blue++;
		else
			white++;
    }
}