[백준] 단계별로 풀어보기(단계:20,분할 정복,JAVA)1780번, 종이의 개수

문제 링크

1780번: 종이의 개수

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

 

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

문제를 살펴보면 종이를 적절한 크기로 자른다는 내용을 살펴보면 분할한다는 내용과 동일합니다.

해결 알고리즘을 살펴보면

1. 처음 종이가 모두가 동일한 숫자 1/0/-1으로 이루어지는지 확인합니다.

2. 하나의 숫자로 이루어지지 못한다면 9분할로 나눕니다.

3. 9분할로 나뉜 종이마다 모두 동일한 숫자 1/0/-1으로 이루어지는지 확인합니다.

4. 위 과정을 반복하여 1/0/-1이 구분되는 종이의 개수를 차례대로 출력합니다.

 

예제 입력을 살펴보면

1. 첫 종이가 모두가 동일한 숫자 1/0/-1으로 이루어지는지 확인합니다.

따로 표를 작성하지 않아도 1/0/-1이 섞여있으므로 하나의 종이가 아닙니다.

2. 9분할하여 분할된 종이들이 모두가 동일한 숫자 1/0/-1으로 이루어지는지 확인합니다.

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

9분할로 나누었지만 모두가 동일한 숫자 1/0/-1이 아니기 때문에 종이가 아닙니다.

0	1	-1
0	-1	1
0	1	-1

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

9분할을 나누면 크기가 모두 1이기 때문에 자신의 숫자가 그에 해당하는 종이가 됩니다.

그래서 1 = 3개, 0 = 3개, -1 = 3개가 됩니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 띄어쓰기 기준으로 입력값을 나누어 배열에 저장하였습니다.
• 종이 개수/종이 확인/종이 개수 더하기을 수행하는 paperCount/paperCheck/countPlus 함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 종이의 개수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• paperCount함수는 위 알고리즘을 재귀를 통해 구현하였으며 화면의 최소크기(1)이 되었을 때는 종이에 숫자에 따라 그대로 개수를 더하였습니다.
• paperCheck는 2중 for문을 사용하여 분할된 화면이 모두 1/0/-1인지 확인하였습니다.
• countPlus는 종이에 적인 숫자에 따라 개수를 더하여주도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[][] paper;	//종이 값 저장 배열
	static int minus = 0, zero = 0, plus = 0;	// 1,0,-1 종이 개수 변수
    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
        //----------입력 값 저장 및 배열 초기화----------
        StringTokenizer st;
        int size = Integer.parseInt(br.readLine());
        paper = new int[size][size];
        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());
        }
        paperCount(0, 0, size);		//함수 실행
        bw.write(minus + "\n" + zero + "\n" + plus + "\n");	//결과 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //--------종이 개수 구하는 함수----------
    public static void paperCount(int start, int end, int size) {
    	if(size == 1) {		//크기가 1일 때
    		countPlus(paper[start][end]);
    		return;
    	}	
    	if(paperCheck(start, end, size))	//모두 1,0,-1로 이루어질 때
    		countPlus(paper[start][end]);
    	else {
        	//---------9분할 진행-------------
    		int tempSize = size/3;
    		paperCount(start, end, tempSize);
    		paperCount(start, end + tempSize, tempSize);
    		paperCount(start, end + (tempSize*2), tempSize);
    		paperCount(start + tempSize, end, tempSize);
    		paperCount(start + tempSize, end + tempSize, tempSize);
    		paperCount(start + tempSize, end + (tempSize*2), tempSize);
    		paperCount(start + (tempSize*2), end, tempSize);
    		paperCount(start + (tempSize*2), end + tempSize, tempSize);
    		paperCount(start + (tempSize*2), end + (tempSize*2), tempSize);
    	}
    	
    }
    //-------종이가 모두 동일한 1,0,-1으로 되어있는지 확인하는 함수---------- 
    public static boolean paperCheck(int start, int end, int size) {
    	int firstValue = paper[start][end];
    	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 n) {
    	if(n==-1)
    		minus++;
    	else if(n==0)
    		zero++;
    	else
    		plus++;
    }
}