백준 웹사이트 "2447번 - 별 찍기 - 10" 문제풀이입니다.
언어는 C언어입니다. (제출 언어: C99)
문제
2447번: 별 찍기 - 10
재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이
www.acmicpc.net
소스 코드
#include <stdio.h>
#include <math.h>
char star[2187][2187];
void make_star(int size, char (*star)[2187], int m, int n); // 1 <= k < 8
int main(void){
int N;
scanf("%d", &N);
make_star(N, star, N-1, N-1);
// star 배열 출력
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(star[i][j]=='*')
printf("%c", star[i][j]);
else
printf(" ");
}
printf("\n");
}
}
void make_star(int size, char (*star)[2187], int m, int n){
if(size==1){
star[m][n] = '*';
}
else{
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
if(i==1 && j==1){
//공백 채움
// [ (m+1)-(size/3)*2 ], [ (n+1)-(size/3)*2 ]
// ~ [ (m+1)-(size/3)-1 ], [ (n+1)-(size/3)-1 ]
for(int c1=(m+1)-(size/3)*2; c1<size/3; c1++){
for(int c2=(n+1)-(size/3)*2; c2<size/3; c2++){
star[c1][c2] = '\0';
}
}
}
else
make_star(size/3, star, (m+1)-(size/3)*i-1, (n+1)-(size/3)*j-1);
}
}
}
}문제 풀이
지금까지 풀어본 '백준: 단계별로 풀어보기' 문제들 중 가장 어렵웠습니다. 재귀적인 패턴으로 별들을 찍는 문제인데, 이때 출력은 재귀적으로 하면 안 된다는 부분이 문제를 어렵게 만듭니다. 만약 재귀함수 'make_star' 안에서 직접 출력까지 한다면, 하나의 정사각형 모양으로 출력이 되지 않고 작은 정사각형들이 여러 줄에 나타납니다. 이를 해결하기 위해 도입한 방법은, 미리 생성한 이중배열에 재귀를 통해 별들을 채운 후 마지막에 이중배열을 출력하는 방법입니다.
먼저 재귀함수 'make_star'부터 살펴봅시다. 입력받는 파라미터들은 총 네 가지입니다. 'size'는 정사각형의 크기로, 1, 3, 9, 27 등 3의 배수입니다. 'char (*star) [2187]'은 미리 선언한 이중배열 star의 포인터로, 재귀함수 내에서 star에 접근할 수 있게 해줍니다. 이때 문제에서 k의 최댓값이 7이므로, 최대 크기 2187로 선언합니다. 물론, 모든 배열 요소를 사용하지 않을 수도 있습니다. 'm' 과 'n'은 이중배열의 인덱스로, 채우고자하는 정사각형의 위치를 의미합니다. 크기가 9인 정사각형을 채우기 위해서, 크기가 3인 정사각형을 총 8개 만들어야합니다. 이때 크기가 3인 정사각형 8개는 모두 다른 위치에 속하게 되므로, 이를 구별하기 위한 것입니다.
재귀함수 'make_star'이 어떻게 작용하는지 예시로 볼까요? 크기가 9인 정사각형을 만들고 싶다고 합시다. 9를 입력하면 N에 9가 저장되므로 Line 11에서 make_star(9, star, 8, 8)이 실행될 것입니다.
1. make_star(9, star, 8, 8) 실행
2. size가 1보다 큼 → Line 30, 31의 for문이 시작됨
3. i=0, j=0 → make_star(3, star, 8, 8) 실행 (Line 43)
3-1. make_star(1, star, 8, 8) 실행 → star[8][8] = '*' (Line 27)
3-2. make_star(1, star, 8, 7) 실행 → star[8][7] = '*' (Line 27)
...
3-5. star[7][7]='\0' (Line 38)
...
3-7. make_star(1, star, 6, 8) 실행 → star[6][8] = '*' (Line 27)
3-8. make_star(1, star, 6, 7) 실행 → star[6][7] = '*' (Line 27)
3-9. make_star(1, star, 6, 6) 실행 → star[6][6] = '*' (Line 27)
4. i=0, j=1 → make_star(3, star, 8, 5) 실행 (Line 43)
4-1. make_star(1, star, 8, 5) 실행 → star[8][5] = '*' (Line 27)
4-2. make_star(1, star, 8, 4) 실행 → star[8][4] = '*' (Line 27)
...
...
7. i=1, j=1 → Line 32의 if문에 의해, 가운데 3×3의 정사각형을 모두 '\0'으로 채움
...
10. i=2, j=1 → make_star(3, star, 2, 5) 실행 (Line 43)
10-1. make_star(1, star, 2, 5) 실행 → star[2][5] = '*' (Line 27)
...
11. i=2, j=2 → make_star(3, star, 2, 2) 실행 (Line 43)
11-1. make_star(1, star, 2, 2) 실행 → star[2][2] = '*' (Line 27)
...
12. Line 30, 31의 for문이 종료됨
조금 이해가 되시나요? 보통 재귀함수의 알고리즘은 이런 식으로 꽤나 복잡합니다. 종이에 9×9 정사각형을 그려 위의 과정을 직접 따라가보면 도움될 것입니다.
위의 과정을 거쳐, Line 11의 make_star 함수 호출이 종료되면, 이중배열 star이 모두 채워집니다. 물론, 2187×2187 개의 배열 요소가 모두 채워지는 것은 아니고, 입력된 N값에 따라 N×N 개의 배열 요소가 채워집니다. 채워진 N×N 개의 배열 요소를 Line 14 ~ 22를 통해 출력하면 아래와 같이 출력이 나타납니다.
27
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
********* *********
* ** ** * * ** ** *
********* *********
*** *** *** ***
* * * * * * * *
*** *** *** ***
********* *********
* ** ** * * ** ** *
********* *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
*** ****** ****** ***
* * * ** * * ** * * *
*** ****** ****** ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
81×81 정사각형은 더욱 아름답습니다.
81
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
* * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * *
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
********* ****************** ****************** *********
* ** ** * * ** ** ** ** ** * * ** ** ** ** ** * * ** ** *
********* ****************** ****************** *********
*** *** *** ****** *** *** ****** *** *** ***
* * * * * * * ** * * * * * * ** * * * * * * *
*** *** *** ****** *** *** ****** *** *** ***
********* ****************** ****************** *********
* ** ** * * ** ** ** ** ** * * ** ** ** ** ** * * ** ** *
********* ****************** ****************** *********
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
* * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * *
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*************************** ***************************
* ** ** ** ** ** ** ** ** * * ** ** ** ** ** ** ** ** *
*************************** ***************************
*** ****** ****** *** *** ****** ****** ***
* * * ** * * ** * * * * * * ** * * ** * * *
*** ****** ****** *** *** ****** ****** ***
*************************** ***************************
* ** ** ** ** ** ** ** ** * * ** ** ** ** ** ** ** ** *
*************************** ***************************
********* ********* ********* *********
* ** ** * * ** ** * * ** ** * * ** ** *
********* ********* ********* *********
*** *** *** *** *** *** *** ***
* * * * * * * * * * * * * * * *
*** *** *** *** *** *** *** ***
********* ********* ********* *********
* ** ** * * ** ** * * ** ** * * ** ** *
********* ********* ********* *********
*************************** ***************************
* ** ** ** ** ** ** ** ** * * ** ** ** ** ** ** ** ** *
*************************** ***************************
*** ****** ****** *** *** ****** ****** ***
* * * ** * * ** * * * * * * ** * * ** * * *
*** ****** ****** *** *** ****** ****** ***
*************************** ***************************
* ** ** ** ** ** ** ** ** * * ** ** ** ** ** ** ** ** *
*************************** ***************************
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
* * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * *
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
********* ****************** ****************** *********
* ** ** * * ** ** ** ** ** * * ** ** ** ** ** * * ** ** *
********* ****************** ****************** *********
*** *** *** ****** *** *** ****** *** *** ***
* * * * * * * ** * * * * * * ** * * * * * * *
*** *** *** ****** *** *** ****** *** *** ***
********* ****************** ****************** *********
* ** ** * * ** ** ** ** ** * * ** ** ** ** ** * * ** ** *
********* ****************** ****************** *********
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
* * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * ** * * *
*** ****** ****** ****** ****** ****** ****** ****** ****** ***
*********************************************************************************
* ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
*********************************************************************************반응형
'코딩 > 백준 BOJ' 카테고리의 다른 글
| [백준/C언어] 2798번 - 블랙잭 (0) | 2022.02.05 |
|---|---|
| [백준/C언어] 11729번 - 하노이 탑 이동 순서 (0) | 2022.02.04 |
| [백준/C언어] 10870 - 피보나치 수 5 (0) | 2022.02.02 |
| [백준/C언어] 10872번 - 팩토리얼 (0) | 2022.02.01 |
| [백준/C언어] 18108번 - 1998년생인 내가 태국에서는 2541년생?! (0) | 2022.01.31 |
