[백준 2448][💛4] 별 찍기(11) (재귀, DFS)

별 찍기 11

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

난이도 👉 골드 4

내 풀이 ⭕

#include <iostream>
using namespace std;

char arr[3072][6143];

void draw(int row, int col)
{
    // 첫번째 줄 (꼭직점에 * 1개)
    arr[row][col] = '*';
    
    // 두번째 줄 (* 2개)
    arr[row + 1][col - 1] = '*';
    arr[row + 1][col + 1] = '*';
    
    // 세번째 줄 (* 5개)
    for(int i = 0; i < 5; i++)
        arr[row + 2][col - 2 + i] = '*';
}

void triangle(int len, int row, int col)
{
    if (len == 3)
    {
        draw(row, col);
        return;  // 리턴의 유무 중요 !!!
    }
        
    triangle(len / 2, row, col);  // 첫 번째 삼각형의 꼭짓점
    triangle(len / 2, row + len / 2, col - len / 2);  // 두 번째 삼각형의 꼭짓점
    triangle(len / 2, row + len / 2, col + len / 2);  // 세 번째 삼각형의 꼭짓점
}

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

    return 0;
}

1. 한 문자를 원소로 하는 전체 배열을 미리 선언해둔다.
   • char arr[3072][6143]
   • 문제에서 k 의 최대값은 10 으로 주어졌으므로 행은 \(3 * 2^10 = 3072\) 행, 열은 \(3072 * 2 - 1 = 6143\) 열로 최대 크기로 배열을 선언해주었다.
2. 미리 전체 배열에 공백을 쫙 넣어준다.
3. triangle(N, 0, N - 1) 일단 가~ 장 큰 삼각형부터 넘긴다. 재귀 호출로 점점 깊이 들어가며 각 3개의 삼각형의 꼭짓점을 인수로 넘긴다.
4. 각 3 개의 삼각형에 대해 재귀 호출 시켜준다.
   • 재귀호출마다 N은 절반으로 줄어들어 종료 조건인 3 에 수렴한다.
   • draw 종료 조건인 N = 3에 다다랐을 때 비로소 * 을 N = 3일때의 모양으로 배열에 넣어준다.

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

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

---

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

맨 위로 이동하기

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