[백준] 단계별로 풀어보기(단계:20,분할 정복,JAVA)1992번, 쿼드트리

문제 링크

1992번: 쿼드트리

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

 

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

문제를 살펴보면 화면을 압축하다는 내용을 살펴보면 분할한다는 내용과 동일합니다.

해결 알고리즘을 살펴보면

1. 처음 화면이 모두 1이거나 0으로 이루어지는지 확인합니다.

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

3. 4분할로 나뉜 화면마다 모두 1이거나 0으로 이루어지는지 확인합니다.

4. 위 과정을 반복하여 1이 출력되는 화면과 0이 출력이되는 화면을 순차대로 출력합니다.

 

예제 입력을 살펴보면

1. 첫 화면이 모두 1이거나 0으로 인지 확인을 합니다.

따로 표를 작성하지 않아도 1과 0이 섞여있으므로 하나의 화면으로 출력을 못합니다.

2. 4분할하여 분할된 화면들이 모두 1이거나 0인지 확인합니다.

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

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

4분할로 나누었지만 1과 0이 섞여있으므로 화면이 출력되지 못합니다.

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

2사분면

1	1
1	1

1사분면

1	1
1	1

3사분면

0	0
0	0

4사분면

0	1
0	1

4분할된 화면에서 1사분면/2사분면은 모두 1이기 때문에 1이 출력되고 3사분면은 0이 출력됩니다.

4사분면은 모두 0이거나 1이 아니어서 4분할을 진행하면 크기가 1이 되기 때문에 각 숫자가 화면에 출력되는 숫자와 동일하게 됨으로써 0101이 순서대로 출력됩니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• for문과 Character.getNumericValue을 이용하여 입력값들을 배열에 저장하였습니다.
• 쿼드 트리/화면 출력 가능을 수행하는 QuadTree/screenCheck 함수를 만들었습니다.
• 함수를 실행시켜 출력되는 화면에 값들을 저장하였습니다.
• BufferedWriter에 화면이 출력되는 결과를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• QuadTree함수는 위 알고리즘을 재귀를 통해 구현하였으며 화면의 최소크기(1)이 되었을 때는 화면에 보이는 숫자를 그대로 출력하도록 하였습니다.
• screenCheck는 2중 for문을 사용하여 분할된 화면이 모두 1이거나 0을 가지는지 확인하도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static StringBuilder sb = new StringBuilder();	//결과 BuilderString
	static int[][] screen;		//화면 숫자 저장 배열
    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());
        screen = new int[size][size];
        for(int i=0;i<size;i++) {
        	String line = br.readLine();
        	for(int j=0;j<size;j++)
        		screen[i][j] = Character.getNumericValue(line.charAt(j));
        }
        QuadTree(0, 0, size);	//함수 실행
        bw.write(sb.toString() + "\n");		//결과 BufferedWriter에 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //---------쿼드 트리 함수-----------
    public static void QuadTree(int start, int end, int size) {
    	if(size == 1) {		//화면 크기가 1인 경우
    		sb.append(screen[start][end]);
    		return;
    	}	
    	if(screenCheck(start, end, size))
    		sb.append(screen[start][end]);	//화면이 출력될 때
    	else {
        	sb.append("(");
    		int tempSize = size/2;
    		QuadTree(start, end, tempSize);		//2사분면
    		QuadTree(start, end + tempSize, tempSize);	//1사분면
    		QuadTree(start + tempSize, end, tempSize);	//3사분면	
    		QuadTree(start + tempSize, end + tempSize, tempSize);	//4사분면
        	sb.append(")");
    	}
    	
    }
    //-----화면이 모두 1이거나 0인 경우를 확인하는 함수--------
    public static boolean screenCheck(int start, int end, int size) {
    	int firstValue = screen[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(screen[i][j]!=firstValue)
    				return false;
    		}
    	}
    	return true;
    }
}