[백준] 2448_별 찍기 - 11 C++

08 Jun 2023 in Study on Coding Test

재귀를 활용하는 문제

정답제출코드

#include <iostream>

#define ROWMAX 3100
#define COLMAX 6200

using namespace std;

char map[ROWMAX][COLMAX];

void recur(int row, int col, int val)
{
    if (val == 3)
    {
        map[row][col] = '*';

        map[row+1][col-1] = '*';
        map[row+1][col+1] = '*';

        for (int i = col-2; i <= col+2; ++i)
            map[row+2][i] = '*';
        
        return;
    }
    
    recur(row, col, val/2);
    recur(row + val/2, col - val/2, val/2);
    recur(row + val/2, col + val/2, val/2);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < 2*N; ++j)
            map[i][j] = ' ';
    }

    recur(0, N-1, N);

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < 2*N-1; ++j)
            cout << map[i][j];
        
        cout << '\n';
    }
    return 0;
}

오랜만에 풀어보는 재귀, 구현문제였다.

이 문제를 풀면서 어려웠던 점은 아래와 같았다.

• 언제 재귀를 마치고 그림을 그리면서 return을 시켜야 할까?
• 어떻게 해야 중앙 상단에서 시작을 하도록 그림을 그릴 수 있을까?

재귀 함수 구조를 아래와 같이 설계하였다.

void recur(int row, int col, int val)
{
    if (val == 3)
    {
        map[row][col] = '*';

        map[row+1][col-1] = '*';
        map[row+1][col+1] = '*';

        for (int i = col-2; i <= col+2; ++i)
            map[row+2][i] = '*';
        
        return;
    }
    
    recur(row, col, val/2);
    recur(row + val/2, col - val/2, val/2);
    recur(row + val/2, col + val/2, val/2);
}

만약에 높이가 3이 되었을 때, row, col 지점을 별로 표시해서

별을 그리는 작업을 하도록 구현을 하고자 하였다.

문제는 각 삼각형의 시작점을 어떻게 찾아가도록 하느냐였다.

삼각형이 쪼개지는 모습을 보면 빈 삼각형을 제외하고 크게 3군데로 쪼개지는 것을 볼 수 있다.

• 높이가 반으로 줄어든 윗 삼각형
• 높이가 반으로 줄어든 아래 왼쪽 삼각형
• 높이가 반으로 줄어든 아래 오른쪽 삼각형

이 역할을 하는 코드가 위 부터 순서대로 아래와 같다.

recur(row, col, val/2); // 높이가 반으로 줄어든 윗 삼각형
recur(row + val/2, col - val/2, val/2); // 높이가 반으로 줄어든 아래 왼쪽 삼각형
recur(row + val/2, col + val/2, val/2); // 높이가 반으로 줄어든 아래 오른쪽 삼각형

그리고 높이, 즉 val 값이 3이 되었을 때 row와 col 값에 따라서 출력하는 과정을 아래와 같이 진행한다.

if (val == 3)
{
    map[row][col] = '*'; // 첫번째 줄

    map[row+1][col-1] = '*'; // 두번째 줄
    map[row+1][col+1] = '*';

    for (int i = col-2; i <= col+2; ++i) // 세번째 줄
        map[row+2][i] = '*';
    
    return;
}

각 map에 따라서 *을 지정해준 다음에 전체를 출력하여 별 찍기를 완성한다.