[BOJ] 별 찍기

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

Level : G5

유형 : 재귀

---

 

재귀는 일반화를 생각하면 코드를 작성해야 한다. 

로직을 하나하나 다 따져보면 무간지옥에 빠져 머릿속이 꼬이고 감도 안온다.

함수를 계속 따라 들어가면 답도 없고, 그냥 딱 재귀적으로 생각해야 한다!

n=1일 때 잘 작동하지?

n=k일 때 잘 작동하지?

그럼 n=k+1일 때도 잘 작동할 것이다.

(출처- 바킹독님)

 

📌 문제 탐색하기

n : 정사각형의 한변의 길이 (3의 거듭제곱, 3의 8승까지)

정사각형의 한변의 길이가 3일 때 가운데 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

 

재귀를 이용해서 문제를 푼다.

 

📌  코드 설계하기

1. 크기 n이 주어졌을 때 정사각형의 한변의 길이가 3이 될 때까지 정사각형을 9등분하여 각각 재귀를 호출한다.

2. 정사각형의 한변의 길이가 3이면 draw 함수를 실행하여, 가운데 공백을 제외한 모든 칸에 별을 찍는다.

 

문제를 풀면서 막히고 해결한 부분은 다음과 같다.

1. 처음에 m 배열을 만들지 않고, draw 함수에서 cout을 이용해서 '별'과 '공백'을 바로 출력하려고 했다.

👉🏻 그러나, 개행처리가 한변의 길이가 3인 정사각형에 대해서 적용되므로 정답의 출력값이 나올 수 없었다.

💡 따라서 배열 m을 만들어 각 값을 모두 저장한 후, 한번에 출력하는 것으로 해결했다.

 

2. 처음에 main 함수에서 m 배열을 초기화하지 않고 진행했다가, 명시적으로 초기화를 진행해줬다. (안해도 되긴 함)

👉🏻 직관적 이해를 위해 초기화를 진행했다.

📌  정답 코드

#include <iostream>
using namespace std;

int n;
char m[6563][6563];

//cout으로 바로 별을 찍는게 아니라 맵을 만들어서 넣어야될 것 같다.

void draw(int y, int x, int n){
    for(int i=y; i< y+n; i++){
        for(int j=x; j< x+n; j++){
            if(i==y+1 && j==x+1){
                m[i][j]=' ';
                continue;
            }
            m[i][j]='*';
        }
    }
}

//나누는 역할
void solve(int y, int x, int z){
    
    if(z==3){  //길이가 3일 때 멈춤
        draw(y, x, z);
        return;
    }

    int n = z/3;

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(i==1 && j==1){
                continue;
            }
            solve(y + n*i, x+ n*j, n);
        }
    }

    //return;
}

int main(){
    cin >> n;

    //0로 초기화
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            m[i][j]='0';
        }
    }

    solve(0, 0, n);

    //배열로 저장하고 한번에 다 출력
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(m[i][j]=='0'){
                m[i][j]=' ';    //0인건 빈 배열로 재정의
            }
            cout << m[i][j];
        }
        cout << "\n";
    }

    return 0;


}

📌  입출력 예시