[백준] 쿼드트리 1992 - 분할정복(DivideAndConquer) JAVA

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

1992번: 쿼드트리

코드설명

분할 정복 문제입니다.

 

문제로직입니다.

1. (0, 0)에서 N 을 가지고서 분할정복 재귀가 실행됩니다.

2. map[N][N] 을 -> 4가지 로 나누어서 각 4분면에 해당하는 값들이 하나의 숫자로 이루어질때까지 재귀가 실행됩니다. ( 이떄 size가 1이면 무조건 하나의 숫자로 이루어지므로, size==1 인경우 따로 처리필요는 없습니다. )

3. 문제에서 "(" 와 ")"의 경우 처리를 하는경우, 재귀의 시작이 이루어질경우 새로운 칸이 분할되는것으로 생각하면 됩니다. 새로운 재귀가 실행될때 "(" 를 삽입하고 해당 레벨의 재귀가 끝날떄 다시 ")" 로 닫아줍니다.

 

이번 코드에서 Character.toString(Character 값) 에 대해 처음 알았습니다.

항상 String.valueOf(Character값)으로 처리했었는데.. 훨씬 직관적으로 작성할 수 있었습니다.

코드

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

public class Main {
	public static int N, M;
	public static char[][] map;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new char[N][N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	divideConquer(0, 0, N);
    	System.out.println(sb.toString());
    }
	
	public static void divideConquer(int r, int c, int size) {
		
		//만약 검사한 구간이 하나의 숫자로 이루어져있다면, 압축성공 ( size == 1 인경우를 따로 고려안해도  size가 1 이면 무조건 한가지의 색으로 이루어져있음 )
		if(checkMap(r, c, size) == true) {
			sb.append(map[r][c]);
			return ;
		}
		sb.append("(");
		int nSize = size / 2;
		divideConquer(r, c, nSize);	
		divideConquer(r, c + nSize, nSize);
		divideConquer(r + nSize, c, nSize);
		divideConquer(r + nSize, c + nSize, nSize);
		sb.append(")");
		
	}
	
	public static boolean checkMap(int r, int c, int size) {
		char standard = map[r][c];
		for(int i=r; i<r + size;i++) {
			for(int j=c;j<c + size;j++) {
				if(map[i][j] != standard) {
					return false;
				}
			}
		}
		return true;
	}
	
	

}

 

 

기저사례로 size == 1로 하고, return 처리하여 완료합니다.

그래야만, 한개로 이루어졌을 경우 isCompressable은 항상 true이기에 같은 숫자가 두번 들어가지 않습니다.

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int INF = 0;
	public static char[][] matric;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		matric = new char[N][N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			matric[i] = st.nextToken().toCharArray();
		}
		
		compress(matric, 0, 0, N);
		System.out.println(sb.toString());
	}
	
	public static void compress(char[][] A, int r, int c, int size) {
		//기저 사례 1 : size가 1이라면 더이상 불가합니다
		if(size == 1) {
			sb.append(A[r][c]);
			return ;
		}
		
		//만약 (r, c) ~ (r + size, c + size) 까지의 사각형이 압축이 가능하다면,
		if(isCompressable(A, r, c, size) == true) {
			sb.append(A[r][c]);
			return ;
		}
		
		//만약 압축이 불가하다면, 재귀적 압축이 시작됩니다.
		sb.append("(");
		int halfSize = size / 2;
		compress(A, r, c, halfSize);
		compress(A, r, c + halfSize, halfSize);
		compress(A, r + halfSize, c, halfSize);
		compress(A, r + halfSize, c + halfSize, halfSize);
		sb.append(")");
		
	}
	
	public static boolean isCompressable(char[][] A, int r, int c, int size) {
		char startNum = A[r][c];
		for(int i=r;i<r + size;i++) {
			for(int j=c;j<c + size;j++) {
				if(startNum != A[i][j] ) {
					return false;
				}
			}
		}
		return true;
	}
	
}

 

 

반환형식을 String으로 하여 각 부분문제의 반환값을 받아서 처리합니다.

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int INF = 0;
	public static char[][] matric;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		matric = new char[N][N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			matric[i] = st.nextToken().toCharArray();
		}
		
		System.out.println(compress(matric, 0, 0, N));
//		System.out.println(sb.toString());
	}
	
	public static String compress(char[][] A, int r, int c, int size) {
		//기저 사례 1 : size가 1이라면 더이상 불가합니다
		if(size == 1) {
			return Character.toString(A[r][c]);
		}
		
		//만약 (r, c) ~ (r + size, c + size) 까지의 사각형이 압축이 가능하다면,
		if(isCompressable(A, r, c, size) == true) {
			return Character.toString(A[r][c]);
		}
		
		//만약 압축이 불가하다면, 재귀적 압축이 시작됩니다.
		int halfSize = size / 2;
		String leftTop = compress(A, r, c, halfSize);
		String rightTop = compress(A, r, c + halfSize, halfSize);
		String leftBottom = compress(A, r + halfSize, c, halfSize);
		String rightBottom = compress(A, r + halfSize, c + halfSize, halfSize);

		return "(" + leftTop + rightTop + leftBottom + rightBottom +")";
	}
	
	public static boolean isCompressable(char[][] A, int r, int c, int size) {
		char startNum = A[r][c];
		for(int i=r;i<r + size;i++) {
			for(int j=c;j<c + size;j++) {
				if(startNum != A[i][j] ) {
					return false;
				}
			}
		}
		return true;
	}
	
}

 

 

추가로 만약 쿼드트리를 Decompress한다면 어떻게 될까?

입력 1
8
((110(0101))(0010)1(0001))

결과 1
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

 

아래의 코드의 핵심은, 

'(' 를 발견한다면, 네 개의 사분면을 모두 돌아야 한다는 것 이다.

만약 해당 칸이 '[0, 1]'라면, 현재 재귀 레벨의 r, c, size를 가지고서 색칠하면 된다.

 

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int INF = 0, index;
	public static char[][] matrix;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
        matrix = new char[N][N];
        String compressedString = br.readLine();

        index = 0;
        decompress(compressedString, 0, 0, N);

        printMatrix(matrix);
    }

	
    public static void decompress(String s, int r, int c, int size) {
        if (size == 1) {
            matrix[r][c] = s.charAt(index++);
            return;
        }

        if (s.charAt(index) == '(') {
            index++;
            int halfSize = size / 2;
            decompress(s, r, c, halfSize);
            decompress(s, r, c + halfSize, halfSize);
            decompress(s, r + halfSize, c, halfSize);
            decompress(s, r + halfSize, c + halfSize, halfSize);
            index++; // ')' 로 닫아주므로 인덱스를 증가시키며 넘어갑니다.
        } else {
            fillMatrix(r, c, size, s.charAt(index++));
            return ;
        }
    }

    public static void fillMatrix(int r, int c, int size, char value) {
        for (int i = r; i < r + size; i++) {
            for (int j = c; j < c + size; j++) {
                matrix[i][j] = value;
            }
        }
    }

    public static void printMatrix(char[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j]);
            }
            System.out.println();
        }
    }
	
}