문제 이해 단계
https://www.acmicpc.net/problem/2447
들어오는 입력 N은 무조건 3의 거듭제곱수로 들어온다(3,9,27...)
그리고 만들어지는 모양에 있는 맵의 전체 크기는 NxN이라고 한다.
패턴의 형식은 정사각형을 9 등분하여 이를 3으로 나누고.. 어쩌고 저쩌고 해서 하는 것 같은데,
사실 그냥 위에 있는 그림과 예시를 보는 게 빠르다.
사실 이 문제는 패턴을 파악하는 것부터가
문제풀이에 시작이기 때문에 문제 접근 단계에서 설명하겠다.
문제 접근 단계
패턴 특징 알아내기
해당 문제는 편하게도 "재귀적인 패턴으로 별을 찍어보자"라고 말해줘서
재귀를 사용해야 한다는 것을 쉽게 유추할 수 있다.
그럼 재귀함수와 해당 별 찍기 패턴을 어떻게든 엮어서 생각해 보자.
일단 재귀함수에서는 자기 자신을 계속 호출해 주다가
결국 어떤 지점에서는 값 반환을 시작해줘야 한다.
뭐 큰 것부터 시작했을 때는 점점 작아지다가
제일 작은 크기일 때는 더 이상 나눌 수 없어 반환하는 것처럼 말이다.
해당 문제에서는 N이 얼마일 때 더 이상 나눌 수 없을까? 바로 3일 때이다.
여기서는 더 이상 나눠줄 수 없다.
여기서 더 나누면 패턴 유지가 안된다.
즉, 해당 모양이 최소단위이고, 모든 패턴은 해당 모양으로 구성되어 있다.
어떻게 이를 확실할 수 있는가?
숫자가 커지면서 해당 형태가 달라질 수도 있지 않나?
일반적인 패턴이라면 그렇겠지만,
이 문제에서 재귀적인 패턴을 사용한다고 했기 때문에 그럴 수밖에 없다.
이를 이용해서 N이 9일 때를 그려보고 분석해 보자.
나온 그림을 최소단위로 끊어보니 이런 식으로 나온다.
한마디로 N이 9 일 때는 N이 3 일 때의 패턴을 9개 쓴 것이다.
그러면 27일 때도 마찬가지일까? 위에 예제케이스로 한번 보자.
이번에는 N이 9 일 때는 초록색 사각형으로 표시했다.
이번에도 똑같은 원리이다.
N이 27일 때의 패턴은 N이 9일 때의 패턴 8개를 합친 것이다.
근데 N이 9일 때의 패턴은
결국 또 N이 3일 때의 패턴으로 이루어져 있다.
이렇게 묶어서 보니 이 문제가 왜 재귀문제인지 알 것 같다.
N이 몇이든 결국엔 재귀호출을 해서
N이 3일 때의 그림을 그리고 이를 토대로 다른 그림을 그려야 한다.
패턴을 어떻게 구현하면 좋을까
패턴의 특징을 알았으니 이번에는 배열을 보자.
전체적으로 보면 정사각형을 9 등분하고 그중 가장 가운데 있는 곳을 비워둔 형태이다.
그리고 정사각형이기 때문에 우리는 가장 가운데 지점의 좌표를 쉽게 구할 수 있다.
다른 부분들도 마찬가지이다.
해당 정사각형의 길이와 시작 좌표만 알고 있다면
한가운데 좌표를 무조건 구할 수 있다.
그리고 이를 이용하여 좌표 중심에서 8방위 방향으로,
새로운 중심과 N/3의 사이즈를 가지는 패턴을 재귀호출 해준다.
이때 새로운 새로운 중심의 좌표는 N/3의 중심 좌표와
N의 중심 좌표를 적절히 활용하여 구할 수 있다.
N = 27일 때를 예시로 들어 설명하겠다.
27 x 27 크기의 맵에서 정가운데의 좌표는
인덱스를 0부터 시작했을 때 (N/2, N/2) = (13,13)이다.
이 중심 좌표를 기점으로 N/3일 때,
즉 9일 때 정사각형을 만들기 위해 8개의 중심 좌표를 구할 것이다.
위치를 고려하지 않고 정사각형이 9 x 9 길이라는 걸 알고 있으면
정가운데 중심 좌표는 (4,4)라는 것을 알 수 있다.
여기서 시작 좌표값만 알 수 있다면 각 위치에서의 중심좌표를 알 수 있다.
이를 27일 때의 중심좌표와 9일 때의 중심좌표를 잘 사용하면 구할 수 있다.
x좌표나 y좌표나 원리는 똑같으므로 일단 y좌표만 구했다.
왼쪽에는 N이 9일 때의 y좌표,
가운데는 N이 27일 때의 y좌표,
오른쪽일 때는 이 2개를 적절히 조합했다.
조합한 방법은
(N이 27일 때의 y 좌표) + (N이 9일 때의 y좌표 x 2)를 사용하였다.
아무튼 이런 식으로 8방향의 중심좌표를 다 구해주고
이 좌표들에 대해 재귀함수를 다 호출해 주면 된다.
그리고 이 값이 최소 길이인 N = 3에 도달했을 때 그림을 그려주면 된다.
문제 구현 단계
// 각각의 중심좌표를 찾는 재귀 함수(x좌표,y좌표,N의 크기)
void findCenter(int x, int y, int number){
// N = 3 일때 별 찍기 함수 실행
if(number == 3) {
draw(x,y);
return;
}
// 왼쪽 모서리부터 시계 방향 순서
int next = number/3;
findCenter(x-next,y-next,next);
findCenter(x-next,y,next); // 12시 방향
findCenter(x-next,y+next,next);
findCenter(x,y+next,next); // 3시 방향
findCenter(x+next,y+next,next);
findCenter(x+next,y,next); // 6시 방향
findCenter(x+next,y-next,next);
findCenter(x,y-next,next); // 9시 방향
}N일 때의 중심좌표를 통해
8개의 새로운 중심좌표를 구해 재귀함수를 호출하는 코드이다.
재귀함수 문제가 늘 그렇듯 코드는 정말 간단하다.
그냥 8방향에 대한 좌표값을 다 계산해 준 다음에 그 좌표와 N 사이즈에 대한 재귀함수를 호출해 준다.
사실 이게 핵심 코드에 끝이다.
밑에는 전체 코드에 대한 설명을 조금 하고 끝마치겠다.
#include <iostream>
#include <algorithm>
using namespace std;
// 최대 크기 넉넉하게 잡음
char map[7000][7000];
// 별 찍기
void draw(int x, int y){
// 8방위를 나타냄
int dx[] = {0,0,-1,1,-1,-1,1,1};
int dy[] = {-1,1,0,0,-1,1,-1,1};
for(int i = 0; i < 8; i++){
int nx = x + dx[i];
int ny = y + dy[i];
map[nx][ny] = '*';
}
}
// 각각의 중심좌표를 찾는 재귀 함수(x좌표,y좌표,N의 크기)
void findCenter(int x, int y, int number){
// N = 3 일때 별 찍기 함수 실행
if(number == 3) {
draw(x,y);
return;
}
// 왼쪽 모서리부터 시계 방향 순서
int next = number/3;
findCenter(x-next,y-next,next);
findCenter(x-next,y,next); // 12시 방향
findCenter(x-next,y+next,next);
findCenter(x,y+next,next); // 3시 방향
findCenter(x+next,y+next,next);
findCenter(x+next,y,next); // 6시 방향
findCenter(x+next,y-next,next);
findCenter(x,y-next,next); // 9시 방향
}
int main(){
// 전체 map을 ' '로 초기화
fill(&map[0][0],&map[7000-1][7000],' ');
int N;
cin >> N;
findCenter(N/2,N/2,N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cout << map[i][j];
}
cout << "\n";
}
}map의 크기를 7000*7000으로 해준 이유는 문제 제한 조건에서 k가 8 이하였기 때문이다.
3^8 = 6561 이어서 그냥 넉넉하게 잡아줬다.
시행착오
처음에는 고민 좀 하다가 그냥저냥 재밌게 푼 문제 같다.
그냥 이 문제는 크게 헤매지는 않았는데
너무 재밌게 풀어서 그냥 풀이를 한번 적어보고 싶어서 블로그에 적었다.
도움이 많이 됐으면 좋겠다.