[BOJ/Python, Java] 백준 1992번 - 쿼드트리

백준 #1992 쿼드트리

1992번: 쿼드트리

 

Python ver.

n = int(input())
grid = [list(input()) for _ in range(n)]

result = []
size = n
def calc(i, j, size):
  if same(i, j, size):
    result.append(grid[i][j])
    return
  else:
    size //= 2
    result.append("(")
    calc(i, j, size)  # 제1사분면
    calc(i, j + size, size)  # 제2사분면
    calc(i + size, j, size)  # 제3사분면
    calc(i + size, j + size, size)  # 제4사분면
    result.append(")")
  
def same(i, j, size):
  ch = grid[i][j]
  for x in range(size):
    for y in range(size):
      dx, dy = i + x, j + y
      if ch != grid[dx][dy]:
        return False
  return True


calc(0, 0, n)
for i in range(len(result)):
  print(result[i], end="")

 

Java ver.

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

public class Main  {
	static int n;
	static String[][] map;
	static String result = "";
	
	public static void calc(int i, int j, int size) {
		if (isSame(i, j, size)) {
			result = result + map[i][j];
			return;
		} else {
			size /= 2;
			result = result + '(';
			calc(i, j, size);  // 제1사분면
			calc(i, j + size, size);  // 제2사분면
			calc(i + size, j, size);  // 제3사분면
			calc(i + size, j + size, size);  // 제4사분면
			result = result + ')';
			
		}
	}
	
	public static boolean isSame(int i, int j, int size) {
		String ch = map[i][j];
		int dx, dy;
		for (int x = 0; x < size; x++) {
			for (int y = 0; y < size; y++) {
				dx = i + x;
				dy = j + y;
				if (!ch.equals(map[dx][dy])) {
					return false;
				}
			}
		}
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		map = new String[n][n];
		for (int i = 0; i < map.length; i++) {
			String[] line = br.readLine().split("");
			for (int j = 0; j < map.length; j++) {
				map[i][j] = line[j];
			}
		}
		
		
		calc(0, 0, n);
		System.out.println(result);
		
		
	}  // end of main
}  // end of class

 

 

• input으로 들어온 배열에 0 또는 1만 있는지 isSame 함수로 검사한다.
  • 0과 1이 모두 있다면 배열을 4분할 하여 재귀 함수를 통해 각 사분면을 또 검사한다.
  • 0 또는 1만 있다면 해당 위치의 배열은 0 또는 1로 압축