[Baekjoon] 1992 - 쿼드트리

📝 문제

 

 

🔑 풀이 과정

· 처음에는 예제가 왜 저렇게 나오는지 이해가 안갔다. 그림을 그려보니 이해가 갔다.

예제 1의 압축 결과를 보면 다음과 같다.

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 결과를 적으면 출력 결과가 나오게 되는 것이다.

 

· 이 문제는 어제 풀었던 색종이 만들기 문제와 똑같은 문제다. 풀이는 저 문제를 참고.

 

· 다만 나같은 경우 괄호를 어디서 붙여야 하는건지가 헷갈렸는데, 압축이 불가능해서 4개의 영역으로 쪼개질때 괄호를 쓴다고 생각하면 된다.

 

 

 

🔓 답안

import java.io.*;

public class Main {

    static StringBuilder sb = new StringBuilder();

    static char[][] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //입력
        int N = Integer.parseInt(br.readLine()); //영상의 크기
        board = new char[N][N]; //영상을 저장할 배열

        //영상 입력받기
        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < N; j++){
                board[i][j] = str.charAt(j);
            }
        }
        //입력 종료

        quadTree(0, 0, N);

        //출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static void quadTree(int row, int col, int size){

        int zeroCount = 0;
        int oneCount = 0;

        //압축이 가능한지 확인
        for(int i = row; i < row + size; i++){
            for(int j = col; j < col + size; j++){
                if(board[i][j] == '0')
                    zeroCount++;
                else if(board[i][j] == '1')
                    oneCount++;
            }
        }

        if(zeroCount == (size * size)){
            sb.append(0);
            return;
        } else if(oneCount == (size * size)){
            sb.append(1);
            return;
        }
        //압축이 가능하다면 압축값 출력 후 메서드 종료
        
        //압축이 불가능하다면 4개의 영상으로 나눈다.
        int newSize = size/2;

        sb.append("(");
        quadTree(row, col, newSize);
        quadTree(row, col + newSize, newSize);
        quadTree(row + newSize, col, newSize);
        quadTree(row + newSize, col + newSize, newSize);
        sb.append(")");
    }

}

 

 

 

🖤 알고리즘 분류

- 분할 정복

- 재귀