[Java] BOJ1922, 백준 - 쿼드트리

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

1992번: 쿼드트리

 

간단한 분할정복 문제이다.

N이 무조건 2의 거듭제곱 꼴로 주어진다.

문제 이름 쿼드트리 그대로 네모를 사등분하여 생각해주면 된다.

네모의 모든 칸이 1또는 0으로 채워져있으면 압축 가능하기때문에, 이 조건을 넣어서 String값을 return해주면 된다.

 

비트 시프팅을 이용하여 아주아주 간단한 소스코드로 풀 수 있다.

import java.io.*;

public class Main {

	private static char[][] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		arr = new char[n][n];
		for (int i = 0; i < n; i++)
			arr[i] = br.readLine().toCharArray();
		System.out.println(go(0, 0, n));
	}

	private static String go(int i, int j, int n) {
		if (n <= 1)
			return String.valueOf(arr[i][j]);

		n >>= 1;
		// 좌상
		String s1 = go(i, j, n);
		// 우상
		String s2 = go(i, j + n, n);
		// 좌하
		String s3 = go(i + n, j, n);
		// 우하
		String s4 = go(i + n, j + n, n);

		// 0만 포함하거나 1만 포함해야함
		// 0과 1 둘다 포함하면 안됨
		if (!(s1.contains("0") && s1.contains("1")) && s1.equals(s2) && s2.equals(s3) && s3.equals(s4))
			return s1;
		else
			return "(" + s1 + s2 + s3 + s4 + ")";
	}
}