[JAVA] 백준 1192 쿼드트리 풀이

 

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

1992번: 쿼드트리

---

풀이 방법

1. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래와 같이 4사분면으로 나누어서 진행한다.

-> 시작 좌표가 x,y 영상의 크기가 N이라면 

1사분면 x: x~x+N/2  |   y: y~y+N/2

2사분면 x:x~x+N/2   |   y:y+N/2~N

3사분면 x:x+N~N/2  |    y: y~y+N/2

4사분면 x:x+N~N/2  |   y:y+N/2~N   로 나눌 수 있다.

 

2.해당 범위가 1 or 0으로 이루어졌는지 알아보기 위해 해당 범위에 있는 값들을 모두 저장했다. 

if (값이 범위의 넓이와 같다면)-> 모두 1로 채워져있음 -> 1 출력

else if (0과 같다면) -> 모두 0으로 채워져 있음 -> 0 출력

else -> 0과 1 섞여있음 -> N을 2로 나누어주고 범위 안에서 다시 4사분면으로 나누어야 함 (재귀)

 

3. 이때, 재귀를 벗어나는 기저조건은 2번과 같다.

 

틀렸던 부분 & 주의할 부분

1. 처음 코드를 짤 때는 4개의 범위를 나눈다는 것은 알고 있었지만, 일단 무조건 4개의 범위로 나눈 후에 진행했기 때문에 코드가 복잡했었음 

2. 해당 범위가 1 or 0으로 이루어졌는지 알아보기 위해 String을 썼음 -> 코드가 지저분함 

3. 괄호를 어떻게 처리해야 할지 감이 오지 않아서 모든 재귀를 부를 때 마다 괄호를 작성함..

4. 답은 맞았지만, 억지로 답에 맞춘 코드였기 때문에 코드를 재작성함

 

Java 최종 코드 

처음 코드

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

public class BOJ_1992_쿼드트리 {
	static StringBuilder sb=new StringBuilder();
	static StringTokenizer st;
	static int[][] map;
	static int cnt_zero;
	static int cnt_one;
	static int cnt;
	static int N;
	static String str;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N= Integer.parseInt(br.readLine());
		map=new int[N][N];
		for(int i=0; i<N; i++) {
			String str=br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j]=str.charAt(j)-'0';
			}
		}
		cnt=0;
		if(N==1) {
			System.out.println("1");
		}else {
			str="(";
			divide(0,0,N);
			str=str.concat(")");
			
			while(true) {
				if (str.contains("(0000)") || str.contains("(1111)")) {
					str=str.replace("(0000)", "0");
					str=str.replace("(1111)", "1");
				}else {
					break;
				}
			}
			System.out.println(str);
		}
	}

	private static void divide(int x, int y, int n) {
		if(n==2) {
			for(int i=x; i<x+2; i++) {
				for (int j=y; j<y+2; j++) {
					str=str.concat(String.valueOf(map[i][j]));
				}
			}
			return;
		}
		
		int len=n/2;
		
		str=str.concat("(");
		divide(x,y,len);
		str=str.concat(")");
		
		str=str.concat("(");
		divide(x,y+len,len);
		str=str.concat(")");
		
		str=str.concat("(");
		divide(x+len,y,len);
		str=str.concat(")");
		
		str=str.concat("(");
		divide(x+len,y+len,len);
		str=str.concat(")");
		
	}
}

재작성한 코드

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

public class BOJ_1992_쿼드트리 {
	static StringBuilder sb=new StringBuilder();
	static StringTokenizer st;
	static int[][] map;
	static int cnt;
	static int N;
	static String str;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N= Integer.parseInt(br.readLine());
		map=new int[N][N];
		for(int i=0; i<N; i++) {
			String str=br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j]=str.charAt(j)-'0';
			}
		}
		cnt=0;
		divide(0,0,N);
		System.out.println(sb);
	}

	private static void divide(int x, int y, int n) {
		cnt=0;
		
		// 어떤 수로 이루어져 있는지 알기 위해 cnt에 현재 값 저장
		for (int i=x; i<x+n; i++) {
			for (int j=y; j<y+n; j++) {
				cnt+=map[i][j];
			}
		}
		
		// 기저조건이 따로 없지만, if~else문이 기저조건
		if (cnt==n*n) {
			// 만약, cnt 값이 넓이와 같다면, 1로 채워져있음
			sb.append(1);
		}else if (cnt==0) {
			// cnt 값이 0과 같다면, 0으로 채워져있음
			sb.append(0);
		}
		else {
			// 1과 0이 섞여있다면, 괄호로 묶어주고 다시 4분할
			sb.append("(");
			int len=n/2;
			divide(x,y,len);
			divide(x,y+len,len);
			divide(x+len,y,len);
			divide(x+len,y+len,len);
			sb.append(")");
		}
	}
}

처음 코드는 지금 보니까 너무 지저분해보인다.. 답을 맞추기 위해 어거지로 짠 코드였다 

재귀에 대해 감이 오는거같기도 하고.. 아직 문제를 더 많이 풀어봐야 할 것 같다.