BEAKJOON / 백준 - JAVA 1992번 쿼드트리

2024.07.07기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 쿼드트리를 이용하여 하나의 ()안에 수로 표현해 출력하는 문제입니다.

 

에제의 일부를 통해 문제를 설명하도록 하겠습니다.

// 예제 1
8
11000011
11000011
00001100
00001100
10001111
01001111
00111111
00111111

 

왼쪽 위의 ()는 이렇게 나오게 됩니다.

이렇게 동일하게 z방향으로 ()가 쌓이면서 진행하게 되는 원리입니다.

 

1. 함수를 생성해 전체 블럭이 하나의 0 또는 1로 구성되어 있다면 ()없이 바로 숫자를 출력해줍니다.

Set<Character> set = new LinkedHashSet<>();
char c = ' ';

// 전체가 1 또는 0 이라면 () 없이 1 또는 0을 출력
for (int i = starty; i < endy; i++) {
    for (int j = startx; j < endx; j++) {
        set.add(video[i][j]);
        c = video[i][j];

        if (set.size() > 1) {
            break;
        }
    }

    if (set.size() > 1) {
        break;
    }
}

 

2. 전체가 하나로 구성되어 있지 않다면, 비디오의 범위가 2x2라면 ()안에 해당 숫자를 출력하게 됩니다.

// 전체가 1 또는 0이 아니라면
if (endy - starty == 2) { // 비디오 사이즈가 2x2 라면 무조건 출력
    Queue<Character> qu = new LinkedList<>();
    set = new LinkedHashSet<>();

    for (int i = starty; i < endy; i++) {
        for (int j = startx; j < endx; j++) {
            qu.add(video[i][j]);
            set.add(video[i][j]);
        }
    }

    if (set.size() == 1) {
        sb.append(qu.poll());
    }

 

3. 만약 2x2보다 크다면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 다시 쿼드 트리를 진행시켜주면서 함수를 재 호출(재귀) 해줍니다.

else { // 2x2 보다 크다면 재귀 호출
    sb.append("(");

    function(starty, endy - (endy - starty) / 2, startx, endx - (endx - startx) / 2); // 왼쪽 위
    function(starty, endy - (endy - starty) / 2, startx + (endx - startx) / 2, endx); // 오른쪽 위
    function(endy + (starty - endy) / 2, endy, startx, endx - (endx - startx) / 2); // 왼쪽 아래
    function(endy + (starty - endy) / 2, endy, startx + (endx - startx) / 2, endx); // 오른쪽 아래

    sb.append(")");
}

 

4. 이렇게 저장된 문자열을 출력해줍니다.

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	static char[][] video;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine()); // 영상의 크기
		
		char[] arr;
		video = new char[n][n];
		
		for (int i = 0; i < n; i++) {
			arr = br.readLine().toCharArray();
			
			for (int j = 0; j < n; j++) {
				video[i][j] = arr[j];
			}
		}
		
		function(0, n, 0, n);
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 쿼드 트리를 확인하는 함수.
	private static void function(int starty, int endy, int startx, int endx) {
		Set<Character> set = new LinkedHashSet<>();
		char c = ' ';
		
		// 전체가 1 또는 0 이라면 () 없이 1 또는 0을 출력
		for (int i = starty; i < endy; i++) {
			for (int j = startx; j < endx; j++) {
				set.add(video[i][j]);
				c = video[i][j];
				
				if (set.size() > 1) {
					break;
				}
			}
			
			if (set.size() > 1) {
				break;
			}
		}
		
		if (set.size() == 1) {
			sb.append(c);
			return;
		}
		
		// 전체가 1 또는 0이 아니라면
		if (endy - starty == 2) { // 비디오 사이즈가 2x2 라면 무조건 출력
			Queue<Character> qu = new LinkedList<>();
			set = new LinkedHashSet<>();
			
			for (int i = starty; i < endy; i++) {
				for (int j = startx; j < endx; j++) {
					qu.add(video[i][j]);
					set.add(video[i][j]);
				}
			}
			
			if (set.size() == 1) {
				sb.append(qu.poll());
			} else {
				sb.append("(");
				
				while (!qu.isEmpty()) {
					sb.append(qu.poll());
				}
				
				sb.append(")");
			}
		} else { // 2x2 보다 크다면 재귀 호출
			sb.append("(");
			
			function(starty, endy - (endy - starty) / 2, startx, endx - (endx - startx) / 2); // 왼쪽 위
			function(starty, endy - (endy - starty) / 2, startx + (endx - startx) / 2, endx); // 오른쪽 위
			function(endy + (starty - endy) / 2, endy, startx, endx - (endx - startx) / 2); // 왼쪽 아래
			function(endy + (starty - endy) / 2, endy, startx + (endx - startx) / 2, endx); // 오른쪽 아래
			
			sb.append(")");
		}
	}
}