bj10944 별 찍기(재귀)
https://www.acmicpc.net/problem/2447
전형적인 재귀 문제이다.
이러한 문제에서 우리가 생각해야 하는 것들은
1. 규칙을 찾는다.
2. 규칙을 조금 더 세분화해서 수치화 한다.
3. 재귀의 탈출 조건을 찾는다.
이 세 가지가 있다.
1. 규칙을 찾는다.
a: "별 하나"가 찍힌다.(1*1)
b: a가 가운데를 비우고 찍힌다.(3*3)
c: b가 가운데를 비우고 찍힌다.(9*9)
d: c가 가운데를 비우고 찍힌다.(27*27)
2. 규칙을 조금 더 세분화해서 수치화 한다.
b: 사이즈가 3*3인 정사각형의 각 인덱스
(0,0) (0,1) (0,2)
(1,0) (1,2)
(2,0) (2,1) (2,2)
c: 사이즈가 9*9인 정사각형의 각 인덱스
(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8)
(1,0) (1,2) (1,3) (1,5) (1,6) (1,8)
(2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8)
(3,0) (3,1) (3,2) (3,6) (3,7) (3,8)
(4,0) (4,2) (4,6) (4,8)
(5,0) (5,1) (5,2) (5,6) (5,8)
(6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8)
(7,0) (7,2) (7,3) (7,5) (7,6) (7,8)
(8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8)
c의 (0,6)에서 b를 찍는다.
(0, 6) (0, 6 + 1) (0, 6 + 2)
(1, 6) (1, 6 + 2)
(2, 6) (2, 6 + 1) (2, 6 + 2)
이런 식이다.
6 + 0에서 6은 시작 인덱스, 0은 size / 3 * 0
6 + 1에서 6은 시작 인덱스, 1은 size / 3 * 1
이런 식이다.
b에서 다시 a로 들어가면
(0, 6)은 size = 1 시작 인덱스 y = 0, x = 6
size가 1일때는 별 하나
(0, 7)은 size = 1 시작 인덱스 y = 0, x = 7
size가 1일때는 별 하나
size = 3이고 시작 인덱스 y = 0, x = 6인 b가 완료되면
(0, 6) (0, 6 + 1) (0, 6 + 2)
(1, 6) (1, 6 + 2)
(2, 6) (2, 6 + 1) (2, 6 + 2)
이렇게 찍힌다.
이것을 정리해보면
size = 9이고 시작인덱스가(0, 0)에서 재귀 메서드 실행 시
size = 3이고 시작인덱스 (0,0), (0,3), (0,6), (3,0), (3,6), (6,0), (6,3), (6,6)로 분기한다.(이중 for문 + nextY,X를 계산하는 식에 의해) => 즉, 위의 여러개의 시작인덱스에서 b를 찍는다.(재귀 메서드를 시작한다.)
size = 3이고 시작인덱스 (0,6)에서 재귀 메서드 실행 시 (0,6), (0,7), (0,8), (1,6), (1,8), (2,6), (2,7), (2,8)로 분기한다.
똑같이 여러개의 시작 인덱스에서 a를 찍는다.(재귀 메서드를 시작한다.)
size = 1일때는 그냥 별하나 찍고 return
이렇게 되면 정답이다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static char[][] map;
static int N;
static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
initialize();
setStar(N, 0, 0);
printStart();
}
private static void printStart() throws IOException {
for(int y = 0; y < N; y++){
for(int x = 0; x < N; x++){
bufferedWriter.write(map[y][x]);
}
bufferedWriter.newLine();
}
bufferedWriter.flush();
}
private static void setStar(int size, int y, int x){
if(size == 1){
map[y][x] = '*';
return;
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if(i == 1 && j == 1)continue;
int next_y = y + (size / 3) * i;
int next_x = x + (size / 3) * j;
setStar(size / 3, next_y, next_x);
}
}
}
private static void initialize() throws IOException {
N = Integer.parseInt(bufferedReader.readLine());
map = new char[N][N];
for(int y = 0; y < N; y++){
for(int x = 0; x < N; x++){
map[y][x] = ' ';
}
}
}
}