C - [백준 2447] 별 찍기 -10 (feat. 재귀)

참고 포스트

https://rnasterofmysea.tistory.com/61

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

도입부 (Introduction) : 재귀적 사고의 필요성 여태까지 컴퓨터정보공학을 전공하면서 알고리즘에 대한 공부가 취약했기 때문에 튼튼한 기초를 잡고자 알고리즘의 기초부터 공부하기 시작했습니

rnasterofmysea.tistory.com

https://rnasterofmysea.tistory.com/64

예제 입력 1

예제 출력 1

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

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

BOJ 2447 별 찍기 -10

문제 2447번: 별 찍기 - 10은 재귀와 분할정복을 사용하는 문제입니다. 이 문제의 목표는 N×NN \times N 크기의 정사각형에 별을 출력하는 것입니다.

문제 이해

입력 조건:
- N은 3^k (8>k≥0)의 형태로 입력됩니다.
- 즉, N=3,9,27,… 형태입니다.
출력 조건:
- 출력은 N×N 크기의 정사각형으로 별을 그립니다.
- 정사각형은 다음과 같은 방식으로 나뉩니다:
  - N=3N = 3:
```
***
* *
***
```
  - N=9N = 9:
```
*********
* ** ** *
*********
***   ***
* *   * *
***   ***
*********
* ** ** *
*********
```
패턴:
- 전체 크기를 3등분하여 정사각형의 각 부분을 재귀적으로 채웁니다.
- 중앙 부분은 공백으로 처리합니다.

Checkpoint

제귀로 코드를 설계하면 디버깅이 힘들기 때문에 코드를 처음부터 꼼꼼하게 작성해야한다는 것을 느낀 문제였습니다. 절차적 코딩에서는 에러가 발생하는 포인트가 명시적으로 출력되기 때문에 해당 부분을 디버깅하면 되는 경우가 많지만,

재귀로 설계된 문제에서는 에러가 명시적이지 않거나 코드 상 에러가 없지만 결과값이 다르기 때문에 해결하기 어렵다는 점입니다..

이번 문제도 로직상 문제가 없었으나 출력 부분의 시퀀스에서 에러가 발생했고 이를 발견하지 못해 답을 보고 해결하게 되었습니다. 재차 강조하자면 코드가 규칙을 잘 준수하는지 확인하고 나서 배열 크기나 인덱스 등 세세한 부분에 더 신경을 써야겠다 생각하게 된 문제입니다. 하단은 코드 작성 중 발견하지 못했던 예입니다.

문제의 조건이 3^k (8>k≥0)이기에 최대값을 3의 7승, 즉 2187로 설정하고 배열을 선언했습니다.

#define MAX 2187
char arry[MAX][MAX];

이후 분할정복(재귀)가 끝난 후 출력하는 과정에서 하단의 코드를 작성하여 백준에 재출하였으나 계속 실패하였습니다.

Mycompiler를 통해 코드를 테스팅할때는 에러가 발생하지 않았기 때문에 어디가 틀렸는지 알아차리기 힘들었습니다.

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

C언어의 문자열 처리의 가장 기본인, 문자열의 종료 신호인 '\0'을 넣지 않은것이 요인이었습니다.

#define MAX 2188

이를 위해 배열을 2187 보다 1 크게 설정하고 각 행의 끝에 null 문자를 추가했습니다.

    for(int i = 0 ; i < N; i++){
        arry[i][N] = '\0'; // 각 행의 끝에 null 문자 추가
        printf("%s\n", arry[i]);
    }

혹은 배열 확장 없이 string.h 헤더 파일에 있는 putchar() 함수를 쓰는 것도 방법입니다.

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            putchar(arry[i][j]);
        }
        putchar('\n');
    }

해당 문제의 핵심 알고리즘을 잘 설계했음에도, 기본에 충실하지 않아 실패를 하고 답을 확인하게 되니 다시 한번 반성하게 되었네요.

문제풀이

배열 초기화 및 출력:
- N×N 배열을 공백으로 초기화합니다.
- 재귀적으로 별을 찍고, 최종적으로 배열을 출력합니다.
재귀적으로 별 찍기:
- N=1,N = 1이 되면 별('*')을 출력합니다.
- 그렇지 않으면, 배열을 N / 3 * N / 3으로 나누고, 9개 구역 중 중앙 구역은 비워둡니다.

구현 코드

#include <stdio.h>
#include <string.h> // memset 사용을 위해 추가

#define MAX 2188
char arry[MAX][MAX];

void recursion(int x, int y, int len){
    //기저 조건
    if(len == 1){
        arry[x][y] = '*';
        return;
    }
    int new_len = len/3;
    for(int i = 0; i < 3 ; i ++){
        for(int j = 0; j < 3; j ++){
            if(i == 1 && j == 1){
                continue;
            } else{
                recursion(x + j * new_len, y + i * new_len, new_len);
            }
        }
    }
    
};

int main() {
    int N = 0;
    scanf("%d", &N);
    memset(arry, ' ', sizeof(arry));
    recursion(0,0,N);

    for(int i = 0 ; i < N; i++){
        arry[i][N] = '\0'; // 각 행의 끝에 null 문자 추가
        printf("%s\n", arry[i]);
    }
    return 0;
}

코드 설명

주요 로직

기저 조건 (Base Case):
- 재귀에서 가장 작은 단위, len=1일 경우 해당 좌표에 별('*')을 찍습니다.
재귀 호출:
- 입력 배열을 3×3의 작은 격자로 나누어 처리합니다.
- 각 격자의 크기는 현재 len의 1/3입니다.
- 격자의 가운데 부분은 비워두고, 나머지 8개의 구역에 대해 재귀 호출합니다.
출력 배열 초기화:
- memset을 사용하여 배열 전체를 공백(' ')으로 초기화합니다.
- 이를 통해 비어 있는 영역이 자동으로 공백으로 출력됩니다.
출력:
- 배열의 각 행 끝에 \0(null 문자)을 추가하여 문자열로 출력합니다.
- 이를 통해 출력 속도를 최적화합니다.

코드의 세부 설명

1. 배열 초기화 (memset)

memset(arry, ' ', sizeof(arry));

배열 arry는 모든 값이 공백으로 초기화됩니다.
배열 크기는 MAX로 설정되며, 이는 3^7 = 2187을 처리하기 위해 충분합니다.

2. 재귀 함수 (recursion)

void recursion(int x, int y, int len) {
    if (len == 1) {
        arry[x][y] = '*'; // 최소 단위에서 별을 찍음
        return;
    }

    int new_len = len / 3; // 현재 크기를 1/3로 나눔
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == 1 && j == 1) {
                // 중앙 구역은 비움
                continue;
            }
            // 나머지 구역에 대해 재귀 호출
            recursion(x + j * new_len, y + i * new_len, new_len);
        }
    }
}

재귀 동작 방식

N×N을 3×3의 격자로 나누고, 각 격자에 대해 재귀 호출.
중앙 격자는 무조건 비우므로 continue로 처리.

3. 출력 부분

for (int i = 0; i < N; i++) {
    arry[i][N] = '\0'; // 각 행의 끝에 null 문자 추가
    printf("%s\n", arry[i]); // 배열의 각 행을 문자열로 출력
}

배열의 각 행 끝에 \0를 삽입하여 문자열로 출력.
printf("%s\n", ...)을 사용해 빠르게 출력.

코드의 흐름

입력받기:
- 사용자로부터 N 값을 입력받습니다.
- N은 3^k 형태의 수로 제한됩니다.
배열 초기화:
- memset으로 배열을 공백으로 채웁니다.
재귀 호출:
- recursion(0, 0, N) 호출로 패턴 생성.
출력:
- 배열의 각 행을 출력.

시간 복잡도

재귀 호출:
- 각 재귀 호출에서 배열을 3×3으로 나누고, 8개의 구역에 대해 재귀 호출합니다.
- 재귀 깊이는 O(log⁡3N)이고, 각 깊이에서 배열의 모든 요소를 처리합니다.
- 총 시간 복잡도는 O(N2)입니다.
출력:
- N×N 배열을 출력하므로 O(N2).

전체 시간 복잡도: O(N2).

실행 예시

입력:

출력:

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

주요 포인트

재귀를 이용해 N×N 배열을 처리.
배열을 공백으로 초기화하여 빈 칸을 자동으로 출력.
출력 시 printf("%s\n")을 이용해 출력 속도 최적화.

'Computer Science > 알고리즘 문제' 카테고리의 다른 글

C - [백준 9663] N-Queen (feat. 백트래킹, DFS) (4)	2025.01.04
C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열) (0)	2025.01.03
C - [백준 1992] 쿼드트리 (feat. 재귀) (1)	2025.01.01
C - [백준1074] Z (feat. 재귀적 사고, 분할정복) (2)	2024.12.31
C - [백준 2630] 색종이 만들기 (feat. 재귀적 사고, 분할정복) (0)	2024.12.30