[백준 2447][🤍1] 별 찍기(10) (재귀, DFS)

별 찍기 10

2447번 문제 👉 https://www.acmicpc.net/problem/2447

난이도 👉 실버 1

내 풀이 ⭕

#include <iostream>
using namespace std;

char arr[6561][6561];

void draw(int row, int col)
{
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            if (!(i == 1 && j == 1))  // 3 X 3 中 i = 1, j = 1인 부분, 즉 가운데부분만 제외하고 * 을 원소로 넣어줌
                arr[row + i][col + j] = '*';
        }
    }
}

void square(int len, int row, int col)  // 좌상단
{
    if (len == 3)
    {
        draw(row, col);
        return;  // 리턴의 유무 중요 !!! ⭐
    }
        
    square(len / 3, row, col);  // 첫 번째 정사각형
    square(len / 3, row, col + len / 3);  // 두 번째 정사각형
    square(len / 3, row, col + 2 * len / 3);  // 세 번째 정사각형
    square(len / 3, row + len / 3, col);  // 네 번째 정사각형
    // ⭐가운데에 있는 다섯 번째 정사각형은 그리지 않는다 ! !⭐
    square(len / 3, row + len / 3, col + 2 * len / 3);  // 여섯 번째 정사각형
    square(len / 3, row + 2 * len / 3, col);  // 일곱 번째 정사각형
    square(len / 3, row + 2 * len / 3, col + len / 3);  // 여덟 번째 정사각형
    square(len / 3, row + 2 * len / 3, col + 2 * len / 3);  // 아홉 번째 정사각형
}

int main()
{
    int N;
    cin >> N;
    
    // 별찍기 전에 미리 전체 배열에 공백 넣어주기 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            arr[i][j] = ' ';
        }
    }
    
    square(N, 0, 0);  // 별 찍기. 가~장 큰 사각형의 좌상단부터 넘기기
    
    // 출력 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << arr[i][j];
        }
        cout << '\n';
    }

    return 0;
}

void 타입의 함수를 재귀 호출하는 경우라도 꼭 종료 조건에서 return;을 반드시 명시 해주어야 한다.

• void라도 return 되는게 없으면 종료되지 않고 계속해서 무한으로 재귀 호출을 하기 때문에 반드시 return을 명시해 종료 시켜주어야 함

1. 한 문자를 원소로 하는 전체 배열을 미리 선언해둔다.
   • char arr[6561][6561]
   • 문제에서 k 의 최대값은 8 로 주어졌으므로 \(3^8 = 6561\) 최대 크기로 배열을 선언해주었다.
2. 미리 전체 배열에 공백을 쫙 넣어준다.
3. square(N, 0, 0) 재귀 호출로 점점 깊이 들어가며 각 사각형의 시작 점(좌상단 끝점)을 인수로 넘긴다.
4. 가운데에 공백으로 이루어진 사각형을 제외 하고 각 8 개의 사각형에 대해 재귀 호출 시켜준다.
   • N은 1씩 줄어들어 종료 조건인 3 에 수렴한다.
   • draw 종료 조건인 N = 3에 다다랐을 때 비로소 * 을 N = 3일때의 모양으로 배열에 넣어준다.

   • 모~~~~든 사각형은 N = 3일때의 모양으로 동일하게 그려지기 때문에 재귀 호출로 가장 깊숙히 들어간 후 그 자리에 N = 3일때의 모양으로 그려준 후 빠져 나오는 것 !

5. 배열을 전부 출력해준다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기