[BOJ] 백준 2447. 별 찍기 - 10

▶문제설명

[BOJ] 백준 2447. 별 찍기 - 10

https://www.acmicpc.net/problem/2447

▶ 설계

---

별이 찍힌 모습에서 규칙을 찾을 수 있다.

N이 3인 경우

N이 9인 경우

N이 27인 경우

규칙이 보이는가?

잘 안보인다면 아래의 그림을 보자.

N에 따라서 균등하게 9등분을 해보면 가운데 부분만 비어있는 모습을 볼 수 있고, 

각 등분된 조각을 또 9등분 해보면 가운데 부분만 비어있는 것을 볼 수 있다. 

더 이상 범위를 나눌 수 없을 때까지 나누면서 가운데 부분을 제외하고 재귀호출하면 문제를 해결할 수 있을 것으로 보인다.

▶ 구현

---

우선 메인문을 작성해보자.

int main(){
    scanf("%d",&N);
    for(int i=0; i<2188; i++)
        for(int j=0; j<2188; j++)
            map[i][j] = ' ';
 
    setStar(0,0,N);
 
    for(int i=0; i<N; i++){
        for(int j=0; j<N ;j++)
            printf("%c", map[i][j]);
        printf("\n");
    }
 
    return 0;
}

line 2~5 는 char형 2차원 배열을 ' '로 초기화 시킨다.

line 7 에서 원하는 위치에 '*'을 찍어줄 setStar 함수를 호출하고

line 9~13 에서 결과를 출력한다.

핵심이 되는 setStar 함수를 보자.

void setStar(int r, int c, int size){
    if(size == 1){
        map[r][c] = '*';
        return;
    }
}

매개변수로는 왼쪽 위 꼭지점의 좌표를 나타내는 r, c 그리고 가로 세로 길이를 나타내는 size가 있다.

3으로 나누어가며 size를 줄여간다고 했을 때 size가 1이 되면 더이상 나눌 수 없으므로 그 위치에 '*'을 찍어주고 함수를 종료하도록 구현하자.

void setStar(int r, int c, int size){
    if(size == 1){
        map[r][c] = '*';
        return;
    }
 
    int m = size/3;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            setStar(r+i*m, c+j*m, m);
        }
    }
}

size를 3으로 나눈 값 m을 이용해서 쪼개어 질 사각형의 왼쪽 위 꼭지점 좌표를 구한다.

2중 포문으로 

for i 0→3 :

for j 0→3 :

위와 같이 반복해주되, i와 j에는 m이 곱해진다고 생각하면 된다.

나누어 질 9개의 사각형의 왼쪽 상단 꼭지점의 좌표는

각각 ( r + i*m, c + j*m )이 되고, 이와 함께 m을 인자로 넣어서 재귀호출 한다.

이러면 전체를 계속 9등분하며 재귀적으로 모두 '*'을 채워 넣게 된다.

그런데 요구 조건을 만족하기 위해서는 등분된 9개의 사각형 중 가운데에는 별이 찍혀있지 않아야한다.

void setStar(int r, int c, int size){
    if(size == 1){
        map[r][c] = '*';
        return;
    }
 
    int m = size/3;
    int cnt = 0;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            cnt++;
            if(cnt != 5)
                setStar(r+i*m, c+j*m, m);
        }
    }
}

이를 해결하기 위해 재귀 호출을 할 때마다 cnt를 0부터 증가시켰다.

cnt가 5가 되었을 때 가운데 좌표를 나타내므로 cnt가 5가 아닌 경우에만 재귀호출 하도록 구현했다.

메인문에서 전체를 ' '으로 초기화 했기 때문에 호출되지 않은 부분은 ' '으로 남아있게 된다.

이처럼 어느 부분에 '*'을 찍어야 하는지만 생각하여 문제를 좀 더 단순하게 볼 수 있다.

▶ 결과

---

▶Solution

---

[소스코드 보기]