[Java Algorithm] 쿼드트리 BOJ #1992

문제

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

1992번: 쿼드트리

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static StringBuilder out = new StringBuilder();
	static int n;
	static String[][] map;
	
	public static boolean check(int depth, int x, int y) {
		String standard = map[x][y];
		for(int i = x; i < x+depth; i++) {
			for(int j = y; j < y+depth; j++) {
				if(!standard.equals(map[i][j])) return false;
			}
		}
		return true;
	}
	
	private static void QuadTree(int depth, int x, int y) {
		if(check(depth, x, y)) out.append(map[x][y]);
		else {
			out.append("(");
			depth /= 2;
			int[] dx = {0, 0, depth, depth};
			int[] dy = {0, depth, 0, depth};
			for(int i = 0; i < 4; i++) {
				QuadTree(depth, x+dx[i], y+dy[i]);
			}
			out.append(")");
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(in.readLine());
		map = new String[n][n];
		for(int i = 0; i < n; i++) {
			map[i] = in.readLine().split("");
		}
		
		QuadTree(n, 0, 0);
		System.out.println(out);
	}
}

👉 분할 정복, 재귀 문제

주어진 2차원 배열 형태의 입력을 4등분하고, (0, 0)에서부터 블록을 옮겨가며 체크해주었다.

(분할 정복이 익숙하지 않은 분들은 BOJ #1074 Z 문제를 이해하시면 더 편할거에용)

 

💡 피드백

• 분할 정복 공부를 위해 Z 문제와 이 문제를 두 번씩 풀었는데,,
  아직도 완벽하게 잘 푸는 느낌은 아닌 듯 싶다.! 더 마니 풀어봐야 할듯