[백준 10994][🤍4] 별 찍기(19) (재귀, DFS)

별 찍기 19

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

난이도 👉 실버 4

1차 풀이 : 반복문 ⭕

#include <iostream>
using namespace std;


int main()
{
   int n;
   
   cin >> n;
   
   for (int i = 1; i <= 2 * n - 1; i++)
   {
       for(int j = 1; j <= i - 1; j++)
       {
            if (j % 2)
                cout << '*';
            else
                cout << ' ';
       }
       for(int j = 1; j <= 2 * (2 * n - 1 - (i - 1)) - 1; j++)
       {
            if (i % 2)
                cout << '*';
            else
                cout << ' ';
       }
       for(int j = 1; j <= i - 1; j++)
       {
            if (i % 2)
            {
                if (j % 2)
                    cout << ' ';
                else
                    cout << '*';
            }
            else
            {
                if (j % 2)
                    cout << '*';
                else
                    cout << ' ';
            }
       }
       cout << '\n';
   }
   
   for (int i = 1; i <= 2 * n - 2; i++)
   {
       for(int j = 1; j <= 2 * n - 2 - i; j++)
       {
            if (j % 2)
                cout << '*';
            else
                cout << ' ';
       }
       for(int j = 1; j <= 2 * i + 1; j++)
       {
            if (i % 2)
                cout << ' ';
            else
                cout << '*';
       }
       for(int j = 1; j <= 2 * n - 2 - i; j++)
       {
            if (i % 2)
            {
                if (j % 2)
                    cout << '*';
                else
                    cout << ' ';
            }
            else
            {
                if (j % 2)
                    cout << ' ';
                else
                    cout << '*';
            }
       }
       cout << '\n';
   }
}

• 첫 번째 for문 i
  • 2 * N - 1 번 돈다. (그림 상에서 큰 빨간 상자)
  • 첫 번째 for 문 j
    • i - 1 번 돈다. (그림 상에서 색칠되지 않은 보라색 상자)
    • 홀수 번째 열은 *, 짝수 번째 열은 공백
  • 두 번째 for 문 j
    • 2 * (2 * n - 1 - (i - 1)) - 1 번 돈다. (그림 상에서 색칠되지 않은 분홍색 상자)
    • 홀수 번째 행은 *, 짝수 번째 행은 공백
  • 세 번째 for 문 j
    • i - 1 번 돈다. (그림 상에서 색칠된 보라색 상자)
    • 홀수 번째 행
      • 홀수 번째 열은 공백
      • 짝수 번째 행은 *
    • 짝수 번째 행
      • 홀수 번째 열은 *
      • 짝수 번째 행은 공백
• 두 번째 for문 i
  • 2 * N - 2 번 돈다. (그림 상에서 큰 주황색 상자)
  • 첫 번째 for 문 j
    • 2 * n - 2 - i 번 돈다. (그림 상에서 색칠되지 않은 보라색 상자)
    • 홀수 번째 열은 *, 짝수 번째 열은 공백
  • 두 번째 for 문 j
    • 2 * i + 1 번 돈다. (그림 상에서 색칠되지 않은 분홍색 상자)
    • 홀수 번째 행은 공백, 짝수 번째 행은 *
  • 세 번째 for 문 j
    • 2 * n - 2 - i 번 돈다. (그림 상에서 색칠된 보라색 상자)
    • 홀수 번째 행
      • 홀수 번째 열은 *
      • 짝수 번째 행은 공백
    • 짝수 번째 행
      • 홀수 번째 열은 공백
      • 짝수 번째 행은 *

2차 풀이 : 재귀 ⭕

#include <iostream>
using namespace std;

char arr[397][397];  // N의 최댓값은 10. 4 * 10 - 3 = 397.

void draw(int len, int row, int col)
{
    for(int i = 0; i < len; i++)
    {
        if (i == 0 || i == len - 1) // 윗 변, 아랫 변
        {
            for(int j = 0; j < len; j++)
                arr[row + i][col + j] = '*';
        }
        else // 높이 : 별 두개만 찍기
        {
            arr[row + i][col] = '*';  // 첫번째 열
            arr[row + i][col + len - 1] = '*';  // 마지막 열
        }
    }
}

void square(int n, int row, int col)
{
    int len = 4 * n - 3;
    
    draw(len, row, col);  // 재귀 전에 현재 지점의 사각형 먼저 그리기! 
    
    if (n == 1)
    {
        return;  // 리턴의 유무 중요 !!!
    }
        
    square(n - 1, row + 2, col + 2);  // 다음 사각형으로 재귀시 다음 재귀 시작 지점 인수로 넘겨주기

}

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

    return 0;
}

• 각 N 재귀 단계마다 그려지는 사각형 크기가 다르므로 재귀 호출 전에 draw 함수를 호출 해주어야 한다.
• 각 정사각형의 길이는 4 * N - 3 이며
• 현재 사각형의 시작 지점을 [row][col]이라고 한다면 다음 재귀의 사각형의 시작점은 [row + 2][col + 2]이다.

---

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

맨 위로 이동하기

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