[백준 / Java] 1992번: 쿼드트리 (실버1)

문제 풀이 날짜: 2023.08.15
포스트 작성일: 2023.08.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

분할 정복

 

키워드

백준 온라인 저지 1992번: 쿼드트리 (실버1)

 

풀이 접근법

• 1 / 4 분할정복 문제이다. 2 x 2 배열이 될 때까지 쪼개는 방식으로 풀이했다. (재귀 호출)
• (0, 0) 칸에서 시작하고 한 변의 절반 (size / 2)만큼 칸을 옮겨가며 재귀를 호출한다.
• 2 x 2 범위 내 비트가 모두 같다면 압축해서 한 자릿수로 나타내고, 서로 다른 비트는 압축하지 않고 모두 나열한다.
• 괄호는 재귀를 시작하면서 열고, 재귀를 마치고 반환받으면서 닫는다.

 

코드

import java.io.*;

public class Main {

	private static int[][] matrix;
	
	private static StringBuilder sb;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());

		matrix = new int[N][N];
		
		sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			String line = br.readLine();
			for(int j = 0; j < N; j++) {
				matrix[i][j] = line.charAt(j) - '0';
			}
		}
		
		quadTree(N, 0, 0);
		
		System.out.println(sb);
	}

	private static void quadTree(int size, int r, int c) {
		//모두 같은 비트라면 압축
		if(isAllSameBit(size, r, c)) {
			sb.append(matrix[r][c]);
			return;
		}
		
		if(size == 2) { // 2 * 2 matrix까지 쪼개졌을 때
			sb.append("(");
			for(int i = r; i < r + size; i++) {
				for(int j = c; j < c + size; j++) {
					sb.append(matrix[i][j]);
				}
			}
			sb.append(")");
			
			return;
		}
		
		sb.append("("); //재귀를 시작하며 괄호 열기
		int newSize = size / 2;
		quadTree(newSize, r, c);
		quadTree(newSize, r, c + newSize);
		quadTree(newSize, r + newSize, c);
		quadTree(newSize, r + newSize, c + newSize);
		sb.append(")"); //4등분 재귀가 끝나면 괄호 닫기
	}

	private static boolean isAllSameBit(int size, int r, int c) {
		int initialBit = matrix[r][c];
		
		for(int i = r; i < r + size; i++) {
			for(int j = c; j < c + size; j++) {
				if(matrix[i][j] != initialBit) return false;
			}
		}
		
		return true;
	}
}

---

 

 

git 링크

(git 링크 첨부)