[Baekjoon/Silver 1/C, C++] 2447번: 별 찍기 - 10

Baekjoon(백준) 2447번: 별 찍기-10

2447번: 별 찍기 - 10

문제 설명

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
***
* *
***
N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 아래 <예제 출력>과 같다.
입력 N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3^k이며, 이때 1 ≤ k < 8이다.

<예제 출력(N=27)>

풀이

위 <예제 출력>을 9등분 해보면 가운데 칸만 비어있다.
가운데를 제외한 다른 칸을 다시 9등분하면 또 작은 칸의 가운데만 비어있다는 것을 알 수 있다.

위 순환(재귀) 규칙을 별(*)로 가득 찬 char형 N*N 2차원 배열 가운데에 N/3 * N/3 크기의 구멍을 뚫는다고 생각하면서 접근해보았다.

별 행렬을 순회하면서 크게 2가지의 경우만 신경쓰면 된다.
(1) 9등분 했을 때 가운데 칸 구멍뚫기
(2) 가운데를 제외한 칸에서 다시 작은 단위로 9등분 하여 작은 구멍 뚫기(순환)

(1)의 경우, 9등분 했을 때 가운데 칸의 구멍은 [N/3, N/3] 위치부터 N/3 * N/3 크기로 뚫는다.
여기서 뚫는다는 것은 '*'로 저장되어있는 원소를 ' '로 다시 저장한다는 의미이다.

(2)의 경우, 가운데를 제외한 칸은 (N/3)*(N/3) 크기로 다시 구멍을 뚫기 위해 재귀 호출을 한다.
이 때, 구현의 편의를 위해 해당 칸의 시작 좌표를 arguments로 전달하였다.

위 규칙을 함수로 구현한 것은 다음과 같다.

/**
 * 별로 채워진 array에 구멍뚫는 함수
 * @param array 구멍을 뚫을 2차원 별('*') 행렬
 * @param n array의 행 길이
 * @param start_x 구멍을 뚫기 위한 별 행렬 영역의 시작 위치 x좌표
 * @param start_y 구멍을 뚫기 위한 별 행렬 영역의 시작 위치 y좌표
 */
void punch_stars(char** array, int n, int start_x, int start_y)
{
    // 구멍을 뚫기 위해 n*n 행렬 순회
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // 9등분 했을 때의 가운데 칸에 (n/3)*(n/3) 크기 구멍 뚫음('*' -> ' '로 저장)
            if((i / (n/3) == 1) && (j / (n/3) == 1)){
                array[start_x+i][start_y+j] = ' ';
            // 가운데를 제외한 칸은 작은 단위 (n/3)*(n/3) 크기의 별 행렬에서 구멍을 뚫기 위해 재귀 호출 (단, n > 3)
            }else if((i % (n/3) == 0) && (j % (n/3) == 0)){
                if (n > 3) punch_stars(array, n/3, start_x+i, start_y+j);
            }
        }
    }
}

 

C++로 구현한 전체 코드는 다음과 같다.
C에서 기본으로 제공되는 함수 및 문법만 사용했기 때문에 C 컴파일러 환경에서도 작동된다.

#include <iostream>

/**
 * 별로 채워진 array에 구멍뚫는 함수
 * @param array 구멍을 뚫을 2차원 별('*') 행렬
 * @param n array의 행 길이
 * @param start_x 구멍을 뚫기 위한 별 행렬 영역의 시작 위치 x좌표
 * @param start_y 구멍을 뚫기 위한 별 행렬 영역의 시작 위치 y좌표
 */
void punch_stars(char** array, int n, int start_x, int start_y)
{
    // 구멍을 뚫기 위해 n*n 행렬 순회
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // 9등분 했을 때의 가운데 칸에 (n/3)*(n/3) 크기 구멍 뚫음('*' -> ' '로 저장)
            if((i / (n/3) == 1) && (j / (n/3) == 1)){
                array[start_x+i][start_y+j] = ' ';
            // 가운데를 제외한 칸은 작은 단위 (n/3)*(n/3) 크기의 별 행렬에서 구멍을 뚫기 위해 재귀 호출 (단, n > 3)
            }else if((i % (n/3) == 0) && (j % (n/3) == 0)){
                if (n > 3) punch_stars(array, n/3, start_x+i, start_y+j);
            }
        }
    }
}

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

    // N*N array 배열 동적 할당
    char** array = (char**)malloc(sizeof(char*)*N);
    for(int i = 0; i < N; i++)
        array[i] = (char*)malloc(sizeof(char)*N);

	// N*N 행렬 전체에 '*' 저장
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            array[i][j] = '*';

	// 구멍뚫기
    punch_stars(array, N, 0, 0);

	// 별 출력
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++)
            printf("%c", array[i][j]);
        printf("\n");
    }

    return 0;
}