C - [백준 1992] 쿼드트리 (feat. 재귀)

참조 포스트

2024.12.27 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 단순 반복을 넘어서: 절차적 사고에 재귀를 더하다

[알고리즘] 단순 반복을 넘어서: 절차적 사고에 재귀를 더하다

 

2024.12.28 - [분류 전체보기] - C - [백준1074] Z (feat. 재귀적 사고, 분할정복)

 

예제 입력 1 

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력 1 

((110(0101))(0010)1(0001))

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

 

[BOJ 1992] 쿼드 트리

BOJ "1992번 쿼드 트리"의 목표는 2차원 배열을 쿼드트리 형식으로 압축하여 출력하는 것입니다.

• 입력
  • 첫 줄에 영상의 크기 N (N은 2^k, 1≤N≤64)가 주어집니다.
  • N×N 크기의 영상이 0과 1로 이루어진 문자열로 주어집니다.
• 출력
  • 주어진 영상을 쿼드트리 형식으로 압축하여 출력합니다.
• 규칙
  • 만약 모든 값이 같다면, 그 값만 출력합니다.
  • 그렇지 않으면, 4개의 부분으로 나누어 각각을 쿼드트리 형식으로 표현합니다.
  • 구분을 위해 각 쿼드트리 표현은 괄호로 묶습니다.

---

Checkpoint

시작 자료가 있기 때문에 재귀조건(recurison case)를 쉽게 정의할 수 있었습니다. 그리고 문제에서 재귀 조건에 대해 이미 정의를 내려주었습니다. 

• 만약 모든 값이 같다면, 그 값만 출력합니다.
• 그렇지 않으면, 4개의 부분으로 나누어 각각을 쿼드트리 형식으로 표현합니다.

https://velog.velcdn.com/images/cindy0857/post/afac0528-e488-40dc-aafc-02fc33043220/image.png

구현 코드

/*
BOJ_1992_쿼드트리
https://www.acmicpc.net/problem/1992


전체 크기 N (2의 제곱수, 1<= N <= 64)

모두 0 이면 0 / 1이면 1
아닐경우 4등분 등분이 나뉠 때마다 "(" ")" 추가
*/
#include <stdio.h>
#define MAX 64
char arry[64][65];

void recursion(int x, int y,int len){
    if(len == 1){
        printf("%c", arry[y][x]);
        return;
    }
    char current = arry[y][x];
    //printf("%d c: %c\n", count++, current);
    int temp = 0;
    
    for(int i = y; i < len + y; i++){
        for(int j = x; j < len + x; j++){
            if(current != arry[i][j]){
                temp = 1;
                break;
            }
        }
        if(temp==1){break;}
    }
    if(temp){
        printf("(");
        recursion(x,y,len/2);
        recursion(x+len/2,y,len/2);
        recursion(x,y+len/2,len/2);
        recursion(x+len/2,y+len/2,len/2);
        printf(")");
        
    }else{
        printf("%c",current);
        return;
    }
}

int main() {
    int N = 0;
    scanf("%d", &N);

    for(int i = 0 ; i < N; i ++){
        scanf("%s", arry[i]);
    }

    recursion(0,0, N);
    return 0;
}

 

코드 설명

전체 구조

• 입력으로 주어진 N×N 크기의 2차원 배열에서 같은 값(모두 0 또는 모두 1)으로 이루어진 영역을 압축합니다.
• 값이 혼합되어 있다면 4등분하여 각각을 재귀적으로 압축합니다.
• 괄호 ()로 4등분된 영역을 감쌉니다.

---

전역 변수

#define MAX 64
char arry[64][65];

• MAX는 문제의 최대 크기 N=64N = 64를 정의합니다.
• arry는 입력받은 2차원 배열을 저장합니다. 각 행의 크기가 N+1N+1인 이유는 문자열로 입력받기 때문에 마지막에 널문자(\0)를 포함해야 하기 때문입니다.

---

recursion 함수

void recursion(int x, int y, int len);

• 이 함수는 배열의 특정 영역(좌측 상단 좌표 (x, y)와 길이 len)을 압축합니다.

기능

 

1.기저 조건

if(len == 1){
    printf("%c", arry[y][x]);
    return;
}

 

• 길이가 1인 경우, 해당 좌표의 값을 출력하고 종료합니다.

2. 값이 같은지 확인

char current = arry[y][x];
int temp = 0;

for(int i = y; i < len + y; i++){
    for(int j = x; j < len + x; j++){
        if(current != arry[i][j]){
            temp = 1;
            break;
        }
    }
    if(temp == 1) { break; }
}

• 현재 영역의 첫 번째 값 current와 나머지 값을 비교합니다.
• 값이 다르면 temp를 1로 설정하고 확인을 중단합니다.

3.압축 가능 여부에 따른 처리

• 값이 모두 같다면 current를 출력하고 종료합니다.
• 값이 다르면 영역을 4등분하여 재귀 호출합니다.

if(temp){
    printf("(");
    recursion(x, y, len/2);                // 왼쪽 위
    recursion(x + len/2, y, len/2);        // 오른쪽 위
    recursion(x, y + len/2, len/2);        // 왼쪽 아래
    recursion(x + len/2, y + len/2, len/2); // 오른쪽 아래
    printf(")");
} else {
    printf("%c", current);
}

 

main 함수

int main() {
    int N = 0;
    scanf("%d", &N);

    for(int i = 0; i < N; i++){
        scanf("%s", arry[i]);
    }

    recursion(0, 0, N);
    return 0;
}

• 첫 번째 줄에서 배열의 크기 N을 입력받습니다.
• 이후 N줄에 걸쳐 2차원 배열의 데이터를 입력받습니다.
• (0, 0)에서 시작하여 길이 N만큼 배열 전체를 recursion 함수로 압축합니다.

---

입력과 출력 예시

입력 1

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

 

출력 1

((110(0101))(0010)(1001)(1001))

 

입력 2

4
1111
1111
1111
1111

 

출력 2

1

 

입력 3

4
1100
1100
0011
0011

 

출력 3

((11)(00)(00)(11))

---

시간 복잡도

• 각 재귀 호출마다 배열을 순회합니다.
• 배열의 크기를 계속 4등분하므로 시간 복잡도는 O(N^2)입니다.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.