백준 2447번: 별 찍기 - 10 (분할 정복)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

주어진 크기에 해당하는 패턴을 구하여라.

---

시간복잡도 어림하기

 시간복잡도 어림이 큰 의미가 없는 문제이므로 시간복잡도 어림은 생략하겠습니다.

---

알고리즘 설계하기

 이 문제와 같이 재귀적인 규칙이 있는 경우에는 재귀 호출에 따라 영역의 크기가 어떻게 변하고, 한 호출에서 어떻게 세부 재귀 호출을 진행하는지를 고민하는 것이 좋습니다.

 

 이 문제의 경우 한 번 재귀 호출을 할 때마다 크기가 1/3씩 줄어들고, 한 호출에서 다시 재귀 호출을 할 때에는 9개의 영역으로 나누어집니다. 이때, 9개의 영역 중 가운데에 있는 영역은 아무것도 출력하지 않는 영역이므로 이 부분만 따로 처리하여 문제를 해결할 수 있습니다.

 

 간단하게 코드 흐름을 작성해봅시다.

1. 현재 영역의 크기가 1이라면 그대로 출력, 함수 종료
2. 현재 영역이 가운데 영역이라면 현재 크기 만큼 빈 공간 출력, 함수 종료
3. 현재 영역을 9등분하고, 각 영역에 대해 재귀 호출을 진행한다.

 

 이를 바탕으로 함수의 파라미터를 결정해 봅시다. 현재 영역의 범위를 나타내기 위해, 지금 위치의 시작 지점과 지금 영역의 크기 변수를 파라미터로 가져야합니다. 또한, 현재 영역이 빈 영역인지 다시 나누어지는 영역인지 확인하기 위한 변수도 필요합니다. 따라서 다음과 같은 형태를 가질 것입니다.

void solve(int y, int x, int size, int val)

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
using namespace std;

int n;
char a[10004][10004]; //출력 정보를 담을 배열
void solve(int y, int x, int size, int val){
    if(size == 1 && val == 1){
        a[y][x] = '*'; return;
    }
    if(val == 0){ //현재 영역이 빈 공간일 때
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++)
                a[y + i][x + j] = ' ';
        }
        return;
    }
    int third = size / 3;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
        	/*가운데 영역은 빈공간임을 명시하여 재귀호출*/
            if(i == 1 && j == 1) solve(y + i * third, x + j * third, third, 0);
            else solve(y + i * third, x + j * third, third, 1);
        }
    }
}
int main() {
    cin >> n;
    solve(0, 0, n, 1);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) cout << a[i][j];
        cout << '\n';
    }
    return 0;
}

 2차원 배열 a는 최종 출력정보를 담는 배열입니다.

 

 이전 단계에서 설계한대로, 현재 영역의 크기가 1인지, 현재 영역이 빈 공간인지 확인하고 해당하는 위치에 적절한 처리를 진행했습니다. 이후 현재 영역을 9등분하고, 가운데 영역일 때에는 val = 0값을 전달하여 빈공간임을 명시해주었습니다.

---