[백준] 1992 쿼드트리

문제링크: www.acmicpc.net/problem/1992

1992번: 쿼드트리

문제를 읽는 순간 분할정복임을 알았다.

 

import java.io.*;
import java.util.*;
public class Main {
	public static int N;
	public static char [][]board;
	
	public static void divide_q(int start_y, int start_x, int square_size) {
		if(square_size==1) {
			System.out.print(board[start_y][start_x]);
			return;
		}
		char start = board[start_y][start_x];
		for(int i=start_y;i<start_y+square_size;i++) {
			for(int j=start_x;j<start_x+square_size;j++) {
				if(board[i][j]!=start) {
					System.out.print("(");
					divide_q(start_y,start_x,square_size/2);
					divide_q(start_y,start_x+(square_size/2),square_size/2);
					divide_q(start_y+(square_size/2),start_x,square_size/2);
					divide_q(start_y+(square_size/2),start_x+(square_size/2),square_size/2);
					System.out.print(")");
					return;
				}
			}
		}
		System.out.print(board[start_y][start_x]);
	}
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		board = new char[N+1][N+1];
		for(int i=0;i<N;i++) {
			String temp = br.readLine();
			for(int j=0;j<temp.length();j++) {
				board[i][j] = temp.charAt(j);
			}
		}
		divide_q(0,0,N);
	}

}