Coding - Algo/Java

[백준] 1992번:쿼드트리 (Java 자바)

jainn 2021. 8. 18. 15:40
728x90

문제

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

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또

www.acmicpc.net

 

 

반례 1.

64
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000100000000000000000000000000000
0000000000000000000000000000000001000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000010000000000000000000000
0000000000000000000000000000000000000000010000000000000000000000
0000000000000000000000000000000000000001111110000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000010000000000000000000000000000000
0000000000000000000000000000000000110000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000111000000000000000000000000000000000000000
0000000000000000000000011000000000000000000000000000000000000000
0000000000000000000000001000000000000000000000000000000000000000
0000000000000000000000001100000000000000000000000000000000000000
0000000000000000000000001110000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000001000000000000000000000000000
0000000000000000000000000000000000010100000000000000000000000000
0000000000000000000000000000000000001000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
(0((((00(0001)(1000))000)0(00(00(0010)0)(0(0100)00))((00(0101)0)0((1100)(1100)00)((1000)000)))0(((0(1100)00)000)000)0)(000((000(0(1101)00))(00((1010)0(1011)0)0)0(((1100)(1000)00)000)))(00(00((000(0001))(00(1001)0)0((1000)000))0)0))

 

 

반례 2.

4
0000
0000
0000
0000
0

 

 

소스코드

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

public class Main {
	static char[][] image;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		image = new char[n][n];
		for(int i=0;i<n;i++) {
			image[i] = br.readLine().toCharArray();
		}
		if(n == 1) {
			System.out.println("("+image[0][0]+")");
			System.exit(0);
		}
		
		image_zip(0, 0, n);
		System.out.println(sb);
	}
	public static boolean check(int x, int y, int size) {
		for(int i=x;i<x+size;i++) {
			for(int j=y;j<y+size;j++) {
				if(image[i][j]!=image[x][y]) {
					return false;
				}
			}
		}
		return true;
	}
	public static void image_zip(int x, int y, int size) {
		if(check(x,y,size)) {
			sb.append(image[x][y]);
			return;
		}
		
		size = size/2;
		sb.append("(");
		image_zip(x, y, size);
		image_zip(x, y+size, size);
		image_zip(x+size, y, size);
		image_zip(x+size, y+size, size);
		sb.append(")");
	}
}
반응형
저작자표시 (새창열림)