[알고리즘] 쿼드트리

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

1992번: 쿼드트리

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] image = new int[N][N];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < N; j++) {
				image[i][j] = Character.getNumericValue(line.charAt(j));
			}
		}
		
		dfs(image);
		System.out.println(sb);
	}

	private static void dfs(int[][] image) {
		int result = 0;
		if ((result = findCompressedNumber(image)) != -1) {
			sb.append(result);
			return;
		}
		
		sb.append("(");
		dfs(divideIntoTopLeftimage(image));
		dfs(divideIntoTopRightimage(image));
		dfs(divideIntoDownLeftimage(image));
		dfs(divideIntoDownRightimage(image));
		sb.append(")");
	}
	
	private static int findCompressedNumber(int[][] image) {
		int number = image[0][0];
		int N = image.length;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (image[i][j] != number) {
					return -1;
				}
			}
		}
		return number;
	}

	private static int[][] divideIntoArrage(int[][] image, int[] start, int[] end) {
		int[][] newImage = new int[image.length / 2][image.length / 2];
		for (int i = start[0]; i <= end[0]; i++) {
			for (int j = start[1]; j <= end[1]; j++) {
				newImage[i-start[0]][j-start[1]] = image[i][j]; 
			}
		}
		return newImage;
	}
	
	private static int[][] divideIntoTopLeftimage(int[][] image) {
		return divideIntoArrage(image, new int[] {0, 0}, new int[] {(image.length - 1) / 2, (image.length - 1) / 2 });
	}
	
	private static int[][] divideIntoTopRightimage(int[][] image) {
		return divideIntoArrage(image, new int[] {0, (image.length - 1) / 2 + 1}, new int[] {(image.length - 1) / 2, image.length - 1});
	}

	private static int[][] divideIntoDownLeftimage(int[][] image) {
		return divideIntoArrage(image, new int[] {(image.length - 1) / 2 + 1, 0}, new int[] {image.length - 1, (image.length - 1) / 2});
	}

	private static int[][] divideIntoDownRightimage(int[][] image) {
		return divideIntoArrage(image, new int[] {(image.length - 1) / 2 + 1, (image.length - 1) / 2 + 1}, new int[] {image.length - 1, image.length - 1});
	}

	
}

나의 풀이

- 재귀에서 기저조건에는 무조건 return을 붙이자!! - 디버깅이 힘들어진다.

- divideIntoArrange에서 end는 끝도 포함되게 순회해야 하는데 이를 간과했다. 이런 인덱싱에 조심하자!!

- '3'을 3으로 바꾸기 위해서는 Character.getNumericValue 메서드를 사용하자