백준 2447번 별 찍기 - 10 [C언어]

문제 출처: https://www.acmicpc.net/problem/2447


Sol)

#include <stdio.h>

void star_re(int row, int column, int N){
    if(N == 0) { //종료 조건
        printf("*");
        return; //return을 써 주지 않으면 아래 if문 조건에서 0으로 나누는 오류가 발생하게 된다.
    }

    if((row / N) % 3 == 1 && (column / N) % 3 == 1)
        printf(" ");
    else
        star_re(row, column, N / 3);
}

int main()
{
    int N;

    scanf("%d", &N);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            star_re(j, i, N);
        }
        printf("\n");
    }

    return 0;
}

 

• 풀이 방향

문제 설명과 출력 결과로 미루어 볼 때, 이 문제는 프랙탈 패턴처럼 같은 패턴이 계속해서 반복되므로 재귀로 풀어야겠다는 생각을 하는 것은 충분히 합리적이다. 재귀로 풀기로 생각했다면 두가지 경우를 생각해 볼 수 있다. 이 문제는 '*' or ' '을 규칙에 따라 검사해 찍는 것이 조건이므로,
1. 출력을 할 때마다, 즉 문자 하나를 찍을 때마다 검사를 하는 방법
2. 전부 '*' 로 찍어 놓고 규칙에 따라 별 문자를 공백 문자로 변환하는 방법
재귀라고 하면 아무래도 깊이를 가져야 하기 때문에(이 문제의 경우에는 N/3 씩 깊이가 깊어질 것이다) 직관적으로 생각해 봤을 때는 2번이 조금 더 쉬워 보인다. 이 경우, N이 3일때 까지의 깊이로 들어가서 N = 3 스코프로 각 자리에 공백을 뚫은 뒤, N = 9 스코프로 다시 검사를 하고, N = 27이상에서도 똑같이 반복하는 식이 되겠다. 하지만 이렇게 할 경우, 배열을 이용해야 하기때문에 메모리를 너무 많이 사용하게 된다. 따라서 우리는 공간적 효율성을 위해 1번 방법으로 풀어야겠다는 생각을 할 수 있다.
그렇다면 문자 하나단위로 검사할 때 어떻게 재귀를 사용할 것인가? 일단 좌표를 잡고 풀어야겠다. 규칙을 찾기 위해서는 각 자리마다 구별되는 이름을 붙일 필요가 있기 때문이다. 또한, 재귀함수 내부를 너무 복잡하게 하지 않게 풀기 위해서는 재귀 호출에 좌표의 증가를 맡기지 말고 for에 맡긴뒤, 재귀함수에는 규칙에 따라 해당 좌표를 검사하는 역할만을 맡긴다.

 

• 풀이

공백이 뚫리는 규칙을 관찰해 보자.
먼저, N = 3일 때는 x % 3 == 1 && y % 3 == 1 일 때 1 * 1 짜리 공백이 가운데 뚫리는 것을 알 수 있다.

N = 9 일 때는 x % 3 == 1 && y % 3 == 1 일 때 3 * 3 패턴의 1 * 1 짜리 공백이 찍히고, x / (N / 3) == 1 && y / (N/3) == 1 일 때 9 * 9 패턴의 3 * 3 짜리 공백이 가운데 뚫리는 것을 알 수 있다.

N = 27 일 때는 x % 3 == 1 && y % 3 == 1 일 때 1 * 1 짜리 공백, (x / (N / 3^2)) % 3 == 1 && (y / (N / 3^2)) % 3 == 1 일 때 3 * 3 짜리 공백, x / (N / 3) == 1 && y / (N / 3) == 1 일 때 9 * 9 짜리 공백이 가운데 뚫리는 것을 알 수 있다.

x % 3 == 1 && y % 3 == 1 을 (x / (N / N))% 3 == 1 && (y / (N / N))% 3 == 1 로, x / (N / 3) == 1 && y / (N / 3) == 1 을 (x / (N / 3)) % 3 == 1 && (y / (N / 3)) % 3 == 1 로 표현하면

(x / (N / 3)) % 3 ==1 && (y / (N / 3)) % 3 == 1 , (x / (N / 3^2)) % 3 ==1 && (y / (N / 3^2)) % 3 == 1 , (x / (N / 3^3)) % 3 ==1 && (y / (N / 3^3)) % 3 == 1 ... (x / (N / N)) % 3 ==1 && (y / (N / N)) % 3 == 1 일 때 공백이 뚫린다는 것을 알 수 있고, 위 코드와 같이 조건문을 식 하나로 통일 할 수 있게 된다.

이제 재귀 함수를 구성해보자.
재귀 함수의 인수는 총 세 개, star_re(row, column, N)가 필요하고, N을 3으로 계속해서 나눠 N이 1이 될 때까지 검사한다. 만일 N이 0이 되면 어떠한 공백이 될 조건도 만족시키지 못하는 좌표라는 의미이므로, 해당 좌표에는 별문자를 찍고 함수를 종료하게 하면 되겠다. 따라서 재귀 함수의 end point는 N == 0 으로 잡았다.

N = 27일 때의 좌표

좌표를 잘 관찰해 보면 재밌는 현상들을 발견할 수 있다. 예를 들면, 3 * 3 공백들의 x 좌표와 y 좌표 / (N / 3^2)의 값이 다시 1, 4, 7 이 나온다. 재귀 호출을 따라가보며 관찰해보자.

 

• 문제에 대한 사견

규칙을 찾아 식을 세우는 것도 쉽지 않았고, 재귀 호출에 x, y좌표의 증감까지 포함시키려고 생각을 하다가 시간을 너무 많이 썼다. 좌표 하나하나마다 재귀가 들어갈 수 있다는 것을 기억해야 겠다. 재귀함수를 잘 짜기 위해서는 재귀를 이용할 부분을 명확히 정의하는 연습을 해야겠다는 것을 배웠다.