[알고리즘] 백준1992 쿼드트리 - 자바

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

1992번: 쿼드트리

 

 

[풀이 코드]

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

public class Main {
	static int N;
	static int[][] array;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		array = new int[N][N];
		for(int i=0; i< N; i++) {
			String str = br.readLine();
			for(int j=0; j<N; j++) {
				array[i][j] = str.charAt(j)-'0';
			}
		}//배열담기
		
		dfs(0, 0, N, N);
		System.out.println(sb);
		
	}
	// 범위를 줄여나가면서 재귀! 
	// 8x8 -> 4x4(왼쪽위) 4x4(오른쪽위) 4x4(왼쪽아래) 4x4(오른쪽아래)
	// 4x4 -> 2x2(왼쪽위) 2x2(오른쪽위) 2x2(왼쪽아래) 2x2(오른쪽아래)
	// 2x2 -> 1x1(왼쪽위) 1x1(오른쪽위) 1x1(왼쪽아래) 1x1(오른쪽아래) <= 한칸부터 append 시작!
	
	static void dfs(int si, int sj, int ei, int ej) {
		//주어진 si,sj(시작인덱스)부터 ei,ej(끝인덱스)까지 압축이 가능한지 탐색 
		boolean flag = true;
		int tmp = array[si][sj];
		for(int i=si; i<ei; i++) {
			for(int j=sj; j<ej; j++) {
				if(tmp != array[i][j]) flag = false; 
			}
		}
		
		if(flag) {//압축 가능 
			sb.append(tmp);
		}else { //압축 불가능
			if(ei-si == 1) {//더 이상 쪼개질 수 없는 1x1칸의 경우 append해준다.
				if(array[si][sj] == 0) sb.append(0);
				else if(array[si][sj] == 1) sb.append(1);
				return;
			}
			
			int mi = (si+ei)/2; // y축 중간값 
			int mj = (sj+ej)/2; // x축 중간값
			
			sb.append('('); //시작 괄호 붙이기
			dfs(si, sj, mi, mj);
			dfs(si, mj, mi, ej);
			dfs(mi, sj, ei, mj);
			dfs(mi, mj, ei, ej);
			sb.append(')'); // 끝 괄호 붙이기
		}
		
	}

}

코테볼떈 갤탭못쓰는데 어쩌지

 

 

• Z문제를 풀어서 그런지 어떻게 풀어야 할지는 감이 잡혔던 분할 정복 문제였다. 
  
  
• 풀이 로직
  1. dfs함수의 매개변수로는 입력받은 NxN배열의 시작 인덱스와 끝인덱스를 넣어준다.
  
  2. dfs함수 입장하자마자 시작인덱스와 끝 인덱스까지 압축을 할 수 있는지 이중 for문을 돌아준다.
      - 압축할 수 있는 경우 StringBuilder에 해당 압축 가능했던 수를 넣어준다. (코드에서는 array [si][sj])
      - 압축할 수 없는 경우라면 else문을 통해 다시 재귀를 돌 준비를 한다.
  
  3. mi, mj는 영역을 분할하기 위함이다. 8x8배열을 4x4(왼쪽 위) 4x4(오른쪽 위) 4x4(왼쪽 아래) 4x4(오른쪽 아래) 배열로 나눈다.
  
  4. 나눈 영역을 다시 재귀를 돌아주며 압축이 불가능하고 ei-si가 1인 경우 즉, 더 이상 쪼개질 수 없는 1x1칸의 경우라면 하나씩 StringBuilder에 append 해주면 된다.
  
  

어제 새벽까지 Z문제 때문에 고생했는데 오늘 보답받은 기분... 오늘은 맘 편히 자야겠다~!