[백준 10993][💛4] 별찍기(18) (재귀, DFS)

별찍기 18

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

난이도 👉 골드 4

내 풀이

1차 풀이 📢 출력 형식이 잘못 되었습니다

#include <iostream>
using namespace std;

char arr[1023][2045];

int getPow(int n, int m)
{
    if (m == 0)
        return 1;
    return getPow(n, m - 1) * n;
}

void draw(int len, int startRow, int startCol, int rowNum, int colNum)
{
    if (len % 2) // 홀수일 때 그리는 방식 : 삼각형
    {
        for (int i = 0; i < rowNum; i++)
        {
            if (i == 0)  // 첫째줄 : 밑변
            {
                for (int j = 0; j < colNum; j++)
                    arr[startRow][startCol + j] = '*';
            }
            else if (i == rowNum - 1)  // 마지막줄 : 꼭짓점 1개
            {
                arr[startRow - i][startCol + rowNum - 1] = '*';
            }
            else // 그 이외 : 각 행마다 2개씩 (빗변)
            {
                arr[startRow - i][startCol + i] = '*';
                arr[startRow - i][startCol + colNum - i - 1] = '*';
            }
        }
    }
    else // 짝수일 때 그리는 방식 : 역삼각형
    {
        for (int i = 0; i < rowNum; i++)
        {
            if (i == 0)  // 첫째줄 : 윗변
            {
                for (int j = 0; j < colNum; j++)
                    arr[startRow][startCol + j] = '*';
            }
            else if (i == rowNum - 1)  // 마지막줄 : 꼭짓점 1개
            {
                arr[startRow + i][startCol + rowNum - 1] = '*';
            }
            else // 그 이외 : 각 행마다 2개씩 (빗변)
            {
                arr[startRow + i][startCol + i] = '*';
                arr[startRow + i][startCol + colNum - i - 1] = '*';
            }
        }
    }
    return;
}

void triangle(int len, int startRow, int startCol)
{
    int rowNum = getPow(2, len) - 1;
    int colNum = getPow(2, len + 1) - 3;
    
    draw(len, startRow, startCol, rowNum, colNum);
    
    if (len == 1)
        return;
        
    if (len % 2)
        triangle(len - 1, startRow - rowNum / 2, startCol + rowNum / 2 + 1); // 홀수일 때, 짝수로 가는 재귀. 이제 1 감소 후 짝수로 재귀하여 역삼각형 그려야함. 홀수면 시작점은 좌하단
    else
        triangle(len - 1, startRow + rowNum / 2, startCol + rowNum / 2 + 1); // 짝수일 때, 홀수로 가는 재귀. 이제 1 감소 후 짝수로 재귀하여 역삼각형 그려야함. 짝수면 시작점은 좌상단
}

int main()
{
    int N;
    cin >> N;
    
    int rowNum = getPow(2, N) - 1;
    int colNum = getPow(2, N + 1) - 3;
    
    // 별찍기 전에 미리 전체 배열에 공백 넣어주기 
    for (int i = 0; i < rowNum; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            arr[i][j] = ' ';
        }
    }
    
    // 재귀 (시작점을 인수로 넘김)
    if (N % 2)
        triangle(N, rowNum - 1, 0);  // 홀수면 시작점은 좌하단
    else
        triangle(N, 0, 0);  // 짝수면 시작점은 좌상단
    
    // 출력
    for (int i = 0; i < rowNum; i++)
    {
        for (int j = 0; j < colNum; j++)
        {
            cout << arr[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

규칙

재귀 : 종료 조건으로 향하도록 수렴해야하며 점점 깊이 들어가는 식!

N 일땐 N 개의 삼각형이 그려지므로 제일 큰 바깥 것 부터 재귀로 점점 깊이 들어가며 그려주면 된다. N = 2일땐, N = 1 일때(* 한개)와 N = 2 일때의 두 삼각형을 같이 그린거고 이런 식!

• N 이 짝수 👉 가장 큰 삼각형은 역삼각형
  • 윗변의 왼쪽 끝점이 시작점. 좌상단
    • row는 \(\) 만큼, col은 만큼 이동
• N 이 홀수 👉 가장 큰 삼각형은 일반 삼각형
  • 밑변의 왼쪽 끝점이 시작점. 좌하단
• 예제 N = 4
  • N = 4 일땐 짝수. 역삼각형.
    • *이 시작하는 지점 👉 역삼각형의 좌상단 [0][0]
      • 윗변부터 시작하여 아래 방향 (row가 증가하는) 으로 배열에 * 를 넣어준다.
    • 역삼각형의 테두리
      • 빗변 * 개수 = 15 👉 \(2^{4} - 1\)
      • 윗변 * 개수 = 29👉 \(2^{5} - 3\)
      • 즉, rowNum = 15, colNum = 29
• 예제 N = 3
  • N = 3 일땐 홀수. 삼각형.
    • *이 시작하는 지점 👉 삼각형의 좌하단 [7][8] = [0][0] + [7][8]
      • 밑변부터 시작하여 위 방향 (row가 감소 하는) 으로 배열에 * 를 넣어준다.
    • 삼각형의 테두리
      • 빗변 * 개수 = 7 👉 \(2^{3} - 1\)
      • 윗변 * 개수 = 13👉 \(2^{4} - 3\)
      • 즉, rowNum = 7, colNum = 13
• … 이런식 !

• 노란색으로 표시한 각 삼각형의 그려지는 시작점. 재귀 호출시 넘겨줄 시작점.

구현 순서

1. 전체 크기 배열을 마련해놓고
2. 재귀 방식으로 알맞는 자리에 *을 배열 원소로 넣는다.
   • draw 함수로 현재 삼각형의 시작 지점으로부터 알맞는 자리에 * 를 배열에 넣어준다.
   • 길이가 1, 즉 N=1 크기의 삼각형까지 재귀했을 경우 종료
   • 재귀! 홀수, 짝수에 따라 시작 지점, 즉 인수가 다르기 때문에 다르게 재귀 호출 해준다.
3. 배열 원소들 쫙 출력

• char arr[1023][2045]
  • 1 <= N <= 10 이므로 최대 크기로 미리 선언해준 배열의 크기는
    • 1023 행 2045 열이 되겠다.
      • \(2^{10} - 1\) 행 \(2^{11} - 3\) 열

출력 형식이 잘못됐던 이유

• 왼쪽은 비교를 위해 ` ` 공백 대신 -을 넣은 내 1차 풀이의 결과 이고
• 오른쪽은 백준 홈페이지에 있는 정답 출력 예제를 드래그 한 모습이다.
• 나는 삼각형의 오른쪽 여백에도 공백 문자 데이터가 출력 된 것을 알 수 있는데, 정답은 사실 오른쪽 여백엔 공백 문자가 출력되지 않아야 하는 것이었다.!
  • 이처럼 출력 형식이 잘못 되었다는 것은 정답은 비슷하나 공백 같은 그런게 좀 달라서 출력 결과물이 완전히 동일하진 않다는 의미이다.
  • 한번 정답 출력 예제를 드래그 해서 확인해보는 습관을 들이자 ㅠ ㅜ

2차 풀이 ⭕

• 삼각형 오른쪽의 여백은 공백으로 그대로 넣되 딱 삼각형 오른쪽 여백은 출력하지 않도록 코드를 바꿔 주었다.

    // 출력
    for (int i = 0; i < rowNum; i++)
    {
        if (N % 2)
        {
            for (int j = 0; j < rowNum + i; j++)
            {
                cout << arr[i][j];
            }
        }
        else
        {
            for (int j = 0; j < colNum - i; j++)
            {
                cout << arr[i][j];
            }
        }
        cout << '\n';
    }

• N 이 짝수, 즉 역삼각형의 경우
  • col 부분은 rowNum + i 까지
• N 이 홀수, 즉 삼각형의 경우
  • col 부분은 colNum - i 까지

---

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

맨 위로 이동하기

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