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

Source

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

예제 입력

27

예제 출력

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

해설

출력 패턴을 구성하는 기본 패턴은 아래와 같다.

(1) 기본 패턴

***
* *
***

이차원 배열이라고 한다면 x=1, y=1인 곳(1, 1)만 스페이스(빈칸)이 입력된다. 이 문양 하나만을 고려한다면,

if (x == 1 && y == 1)
    printf(" ")

라는 조건문을 사용하여 간단히 출력할 수 있다. 그런데 문제는 이 기본 문양이 그대로 뻥튀기가 된다는 점이다. 이 문양이 반복되면 아래와 같다.

(2) 기본 패턴의 횡 반복

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

스페이스가 오는 곳의 좌표만 나열하면 (1, 1), (1, 4), (1, 7), (1, 10), (1, 13) ...이 된다. 우선 y값의 변화에 집중해 보면, 1, 4, 7, 10 ... 으로 앞의 수에서 3씩 증가하고 있음을 알 수 있다. y값을 3으로 나눈 나머지가 1인 경우인 것이다. 이를 수식으로 표현하면 (y % 3) == 1이다. 아래로 반복되면 (1, 1), (4, 1), (7, 1), (10, 1), (13, 1) ...이 될 것이므로 y값 수식은 x값 수식으로 그대로 쓸 수 있다. 위의 문양에서 빈칸이 출력되는 조건은 if ((x % 3) == 1 && (y % 3) == 1)이 된다.
자 다음은 9가 초기값으로 입력되었을 때의 문양이다.

(3) 기본 패턴의 확대

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

(1)에 비해서 복잡해진 듯하지만 (1)과 동일한 패턴이다. (1)의 * 하나가 (1) 패턴으로 치환된 모습이다. 물론 빈칸 하나도 (1) 크기의 빈 공간으로 바뀌었다. 이는 27의 경우에도 동일하다. 즉 이때는 9의 패턴이(위 '기본 패턴의 확대') *로 치환되는 것이다. 즉 기본 패턴이 반복해서 호출되는 방식으로 출력 패턴이 완성된다.
우선 '기본 패턴의 확대'에서 빈 공간이 만들어지는 조건을 찾아 보자. 앞서와 같이 중앙 빈컨의 좌표를 적어보면 아래와 같다.

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

(3, 3) (4, 3) (5, 3) (12, 3) (13, 3) (14, 3) (21, 3) (22, 3) (23, 3)
(3, 4) (3, 4) (5, 4) (12, 4) (13, 4) (14, 4) (21, 4) (22, 4) (23, 4)
(3, 5) (4, 5) (5, 5) (12, 5) (13, 5) (14, 5) (21, 5) (22, 5) (23, 5)

x값은 {3, 4, 5}, {12, 13, 14}, {21, 22, 23}로 변화한다. 한 묶은 안은 3, 4, 5로 변화한다. 이 수들은 3으로 나누었을 때 몫이 1이라는 공통적을 가지고 있다. 다음은 12, 13, 14인데 이는 3으로 나누었을 때 그 몫이 4, 그 다음으로 21, 22, 23인 경우에는 그 몫이 7이라는 공통점을 갖는다. 1, 4, 7 ... 눈에 익은 배열이다. (2)에서 빈칸을 출력하게 되는 조건을 찾을 때 본 배열이다. 즉 (2)에서 찾아낸 if ((x % 3) == 1 && (y % 3) == 1)를 사용할 수 있겠다. 그런데 이것은 x값을 3으로 나눈 결과에 대한 조건이므로 x를 3으로 나누는 부분이 보완되어야 한다. 이를 보완하여 수식을 다시 만들면, if ((x / 3) % 3 == 1 && (y / 3) % 3 == 1)이 된다(y값도 동일한 변화를 보이기 때문에 자세한 설명은 생략한다).
이제 한 고비를 넘었다. 이젠 찾아낸 조건을 사용해서 코드를 완성하는 게 남았다.

1. 3의 배수 num을 입력받는다.
2. 좌표값을 입력받아 해당 좌표가 각 3의 배수의 단계(3, 9, 27, 81 ... 물론 확인은 역순으로 이루어지겠지만)마다 빈칸을 찍어야 하는 좌표인지를 반복적으로 확인해야 한다.
   • if ((x / num) % 3 == 1 && (y / num) % 3 == 1) 조건을 충족하면, 빈칸 출력.
   • 그렇지 않고 num / 3이 0이며 * 출력
   • 이때 num이 3의 배수가 아니라면 num을 3을로 나눈 값으로 해당 좌표가 빈칸을 출력할지 확인

앞에서는 x, y를 3으로 나누었으나 재귀 함수를 만들 때는 num을 이용한다. num이 3의 배수이므로 이것으로 나누어도 조건의 결과에는 변화가 없으며 *을 찍는 경우와 재귀 호출을 위한 조건을 지정하기 위해서이다.

1  void star(int x, int y, int num)
2  {
3      if ((x / num) % 3 == 1 && (y / num) % 3 == 1) {
4          printf(" ");
5     } else {
6         if (num / 3 == 0) {
7            printf("*");
8         } else {
9            star(x, y, num / 3);
10         }
11     }
12 }

전체 크기(num)이 9이고 (1, 1)인 경우로 검증해 보자. 첫 루프 3번 라인에서는 (1 / 9) % 3은 1이 아니므로 라인 6으로 넘어간다. 그런데 9 / 3은 0이 아니므로 다시 라인 9으로 넘어가서 다음 3의 배수 단계를 확인하기 위해서 (1, 1, 3)으로 인자가 바뀌어 자기 자신을 다시 호출한다. 라인 3을 충족하지 못하고 다시 라인 6을 거쳐 라인 9로 와서 인자를 (1, 1, 1)로 바꾸어 채귀 호출을 한다. 라인 3에서 (1 / 1) % 3 == 1이 충족되므로 빈칸을 출력하고 재귀 함수 star는 종료된다. 한편 별이 찍히는 (0, 0)의 경우는 위와 동일하게 두 번째 루프 num = 1이 되었을 때 라인 6에서 if 조건을 충족하여 *을 출력하다.
이 제귀 함수를 이용해 전체 코드를 완성하면 아래와 같다.

소스코드: C

#include <stdio.h>

void star(int x, int y, int num)
{
    if ((x / num) % 3 == 1 && (y / num) % 3 == 1) {
        printf(" ");
    } else {
        if (num / 3 == 0) {
            printf("*");
        } else {
            star(x, y, num/3);
        }
    }
}

int main(int argc, char *argv[])
{
    int x, y, num;
    scanf("%d", &num);

    for (x = 0; x < num; ++x) {
        for (y = 0; y < num; ++y) {
            star(x, y, num);
        }
        printf("\n");
    }
    return 0;
}