[*1992*] 쿼드트리 in Java

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

1992번: 쿼드트리

---

 

문제 접근 방식

-> 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단이 모두 0이면 : 0으로 압축

-> 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단이 모두 1이면 : 1으로 압축

-> 왼쪽 상단(0), 오른쪽 상단(1), 왼쪽 하단(0), 오른쪽 하단(1),

즉 0과 1이 섞여 있는 경우면: 0101로 출력

 

---

 

시행 착오

-> 재귀함수를 사용해야 한다는 건 파악했으나

재귀함수를 구성하는 과정에서 어려움을 겪음 ㅜㅜ

 

해당 사이즈의 크기가 모두 0이거나 1이면 0이나 1로 압축한 뒤 재귀를 빠져나온다.

 

하지만, 0과 1이 섞여있는 경우라면 

size를 반으로 줄이고

현재 위치에서의 왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단의 위치를 기준으로

재귀를 다시 호출한다.

=> 이 부분을 떠올리기가 힘들었다.

 

그냥 간단하게 생각하면 됐는데,너무 재귀 끝까지 파고들려고 하는 게 문제인 것 같다.

 

 

그냥 간단하게 생각해서

해당 칸을 압축할 수 있으면 거기서 재귀 스탑

압축을 못하면 해당 칸을 4분할해서

또 다시 재귀를 호출하는 방식이다.

 

 

 

 

---

소스 코드

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {    
    static int[][] map;
    static int N;
    static StringBuilder sb= new StringBuilder();
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        
        for (int i = 0; i < N; i++) {
            char[] tempArr=br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                map[i][j]=tempArr[j]-'0';
            }
        }
        quadTree(0,0,N);
        System.out.println(sb);
        
    }
 
 
 
    private static void quadTree(int x, int y, int size) {
        if(isPossible(x, y, size)) {
            sb.append(map[x][y]);
            return;
        }
        
        int newSize=size/2; // 사이즈 줄이
        sb.append("("); // 
        quadTree(x, y, newSize); // 왼쪽 상단
        quadTree(x, y+newSize, newSize); // 오른쪽 상단
        quadTree(x+newSize, y, newSize); // 왼쪽 하단
        quadTree(x+newSize, y+newSize, newSize); // 오른쪽 하단
        sb.append(")"); 
    }
 
 
 
    private static boolean isPossible(int x, int y, int size) {
        int value=map[x][y];
        
        for (int i = x; i < x+size; i++) {
            for (int j = y; j < y+size; j++) {
                if(value!=map[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

 

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

public class Main {	
	static int[][] map;
	static int N;
	static StringBuilder sb= new StringBuilder();
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		map=new int[N][N];
		
		for (int i = 0; i < N; i++) {
			char[] tempArr=br.readLine().toCharArray();
			for (int j = 0; j < N; j++) {
				map[i][j]=tempArr[j]-'0';
			}
		}
		quadTree(0,0,N);
		System.out.println(sb);
		
	}



	private static void quadTree(int x, int y, int size) {
		if(isPossible(x, y, size)) {
			sb.append(map[x][y]);
			return;
		}
		
		int newSize=size/2; // 사이즈 줄이
		sb.append("("); // 
		quadTree(x, y, newSize); // 왼쪽 상단
		quadTree(x, y+newSize, newSize); // 오른쪽 상단
		quadTree(x+newSize, y, newSize); // 왼쪽 하단
		quadTree(x+newSize, y+newSize, newSize); // 오른쪽 하단
		sb.append(")"); 
	}



	private static boolean isPossible(int x, int y, int size) {
		int value=map[x][y];
		
		for (int i = x; i < x+size; i++) {
			for (int j = y; j < y+size; j++) {
				if(value!=map[i][j]) {
					return false;
				}
			}
		}
		return true;
	}
}