[Baekjoon] 1992 쿼드트리 (S1, 분할정복) - Java

링크

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

 

 

문제 해석

배열 전체를 바라봤을 때 모두 0이거나 1일 때 해당 값을 출력함

만약 배열 전체가 0또는 1로 이뤄져 있지 않을 때, 해당 배열을 4개로 쪼개서 다시 배열을 확인함, 단 쪼개지는 경우 괄호로 묶어서 표시함 

 

 

 

코드

package algo.bj.s1_1992;

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

public class Main {
	static int[][] arr;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		sb = new StringBuilder();

		int N = Integer.parseInt(st.nextToken());

		arr = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String s = st.nextToken();
			for (int j = 0; j < N; j++) {
				arr[i][j] = s.charAt(j) - '0';
			}
		}

		// 탐색 할 한 변의 넓이, 시작 x, 시작 y
		recursive(N, 0, 0);
		System.out.println(sb);

	}

	private static void recursive(int n, int startX, int startY) {
		// basis part
		if (n == 1) {
			if (arr[startX][startY] == 0) {
				sb.append(0);
			}
			if (arr[startX][startY] == 1) {
				sb.append(1);
			}
			return;
		}

		int count = 0;
		// inductive part
		for (int i = startX; i < startX + n; i++) {
			for (int j = startY; j < startY + n; j++) {
				count += arr[i][j];
			}
		}

		if (count == 0) {
			sb.append(0);
		} else if (count == n * n) {
			sb.append(1);
		} else {
			sb.append("(");
			recursive(n / 2, startX, startY);
			recursive(n / 2, startX, startY + n / 2);
			recursive(n / 2, startX + n / 2, startY);
			recursive(n / 2, startX + n / 2, startY + n / 2);

			sb.append(")");
		}

	}
}

 

 

 

코드 해석

- 예시1

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

만약 예시 1과 같이 모든 값이 0으로 나온다면 출력 결과로 0 이 나오게 됩니다.

 

 

- 예시 2

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

 

하지만 예시2와 같이 배열이 존재한다면, 한번에 표현하지 못하므로 ()로 묶고,
나뉜 네가지 영역을 다시 확인해야 합니다.

이때 네 영역은 각각 1 0 0 1로 표현가능하므로 (1001) 이 나오게 됩니다.

 

 

이를 재귀를 통해서 반복하여 확인하도록 구현하였습니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice