[백준/boj] 1992: 쿼드 트리 (Java) / 분할 정복/ 재귀

문제

1992번: 쿼드트리

풀이

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

public class Main {

	private static int N;
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	private static char[][] map;
	private static char c;

	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		map = new char[N][N];
		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}
		solve(0, 0, N);
		bw.flush();
		bw.close();
	}

	private static boolean check(int x, int y, int n) {
		c= map[x][y];
		for (int i = x; i < x + n; i++) {
			for (int j = y; j < y + n; j++) {
				if (map[i][j] != map[x][y])
					return false;
			}
		}
		return true;
	}

	private static void solve(int x, int y, int n) throws Exception {
			if(check(x, y, n)) {
				bw.append(c);
			} else {
				bw.append("(");
				int max = n / 2; 
				for (int i = 0; i < 2; i++) {
					for (int j = 0; j < 2; j++) {
						solve(x + max * i, y + max * j, max);
					}
				}
				bw.append(")");
			}
	}
}

 

분할 정복을 이용해서 푸는 문제이다. solve에서 계속 8 > 4 > 2 와같은 방식으로 n 을 줄여가며 check 함수를 호출한다.

check 함수

1. 첫번째 요소를 저장하고 만약 첫번째 요소와 다르다면 false를 return 한다.

• n 을 /2 하고 check를 또 호출한다. 
• 만약 max(n/2)가 1인 경우에는 무조건 true를 호출하게 되기 때문에 요소하나하나를 출력하게 된다.

2. 첫번째 요소와 모든 요소들이 같다면 true를 return한다.

• 사분면의 요소들이 모두 첫번째 요소와 같다는 것이므로 하나로 합축해서 출력한다.

 

좌표에서 분할 정복을 사용하는 방식이 비슷하므로 코드에 익숙해지는것이 중요할 것 같다 !!

비슷한 문제로 별찍기 등의 문제도 풀어봐야겠다.