백준 1992. 쿼드트리

🅰 백준 1992. 쿼드트리

1992번: 쿼드트리

✏️ 문제 풀이

• 영상이 4개로 압축되어 진행되므로 4개의 시작점을 구해서 재귀를 돌려주었다.
• 또한 출력을 맞춰주기 위해 재귀가 시작되기 전에 "("를 출력해주고, 재귀가 끝나면 ")"를 출력해주었다.

✏️ 소스코드

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

public class Main {
	static int N;
	static int tree[][];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int treecnt = 0;
		tree = new int[N][N];

		// 데이터 입력
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				tree[i][j] = str.charAt(j) - '0';
				if (tree[i][j] == 1)
					treecnt++;
			}
		}
		if (treecnt == N * N)
			System.out.println(1);
		else if (treecnt == 0)
			System.out.println(0);
		else {
			quardTree(0, 0, N);
		}
	}

	static void quardTree(int start_x, int start_y, int n) {
		int check = tree[start_x][start_y];
		boolean a = false;

		Loop1: for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (tree[start_x + i][start_y + j] != check) {
					a = true;
					break Loop1;
				}
			}
		}

		if (!a) {
			System.out.print(check);
		} else {
			System.out.print("(");
			quardTree(start_x, start_y, n/2);
			quardTree(start_x, start_y + n / 2, n / 2);
			quardTree(start_x + n / 2, start_y, n / 2);
			quardTree(start_x + n / 2, start_y + n / 2, n / 2);
			System.out.print(")");
		}
	}
}

 

✅ 후기

•