[백준] 2447번 별찍기 - 10 (JAVA)

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

2447번: 별 찍기 - 10

 

• 문제 이해
• 해결 방법
• 코드 구현

 

---

문제 이해

 

금방 해결할 수 있을 줄 알았는데 생각보다 시간이 걸린 문제다.

일단 문제 자체에서 재귀적인 패턴으로 해결하라고 명시되어있다.

아마 명시되어있지 않더라도 문제를 읽어보면서 3^n이 입력으로 들어오는 조건이 있을 때 입력/3으로 나누어지니 재귀를 파악할 순 있다.

예를 들어 입력이 27이라면 별이 그려지는 부분이 27 -> 9 -> 3 -> 1으로 3으로 나누어져 그려지므로

재귀적인 방법을 사용해야 한다는 걸 금방 알아챌 수 있을 것이다.

 

 

---

해결 방법

 

일단 3^N인 수를 입력받으면 행 3개, 열 3개 총 9개 부분으로 나눈 후 재귀적으로 해결해야 한다.

그러므로 재귀 함수의 선언부를 (행의 마지막 위치, 열의 마지막 위치, 3으로 나눌 size)로 만들었다.

행, 열을 마지막 위치가 아닌 시작 위치로 해도 무관하다.

중요한 점은 3으로 나눈 size만큼 더해주거나 빼주면서 아홉 부분을 재귀 함수를 호출한다는 것이다.

9                            
3,        6,        9
1, 2, 3  4, 5, 6  7, 8, 9

 

여기서부터 size/3을 간격이라고 하겠다.

입력이 9라고 예를 들면 3^n을 입력으로 받으므로 9에서 간격인 3씩 빼는 방식을 선택했다. 이 숫자를 행, 열 따로 재귀적으로 넘겨주면 된다.

직접 구현해보진 않았지만 3, 6, 9로 넘겨주지 않고 시작 위치부터 간격을 더하면서 1, 4, 7을 함수의 인자로 넘겨줘도 해결될 것 같다.

 

구현하면 반복이 될 때마다 행과 열을 간격만큼 빼주면서 총 9 부분을 호출하도록 이중 반복문을 사용했다.

그리고 정 가운데 부분은 별을 그리지 않을 것이므로 정 가운데 부분에 해당되는 부분은 재귀 함수를 호출하지 않도록 했다.

 

재귀 함수의 종료 조건은 size가 1이 되면 재귀 함수를 종료하게 끔 하였다.

행, 열의 크기가 1이므로 이 부분에서 전역 변수로 선언된 2차원 배열[입력 크기][입력 크기]에 별을 그려주면 된다.

 

급하게 생각하지 말고 2차원 배열의 index를 유지시키면서 해당 행과 열 지점을 재귀 함수로 넘겨 호출을 해주고

재귀 함수의 종료 조건만 잘 지정해준다면 풀렸던 문제였다.

결국 중요한건, for문을 이용한 index 증감 조절을 잘해주면 된다. 

 

이 외에도 재귀 함수를 이용한 비슷한 문제들이 백준에 있는데

재귀 함수 호출 시에 넘겨줄 index만 잘 생각해서 범위 조정해준다면 전부 해결할 수 있다.

 

 

---

코드 구현

 

import java.util.*;
import java.io.*;
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuffer sb = new StringBuffer();
    static String[][] str;
 
    public static void main(String[] args) throws IOException {
        int input = Integer.parseInt(br.readLine());
        str = new String[input][input]; 
        for(String[] aa : str)
            Arrays.fill(aa, " "); // NullpointerException 방지
 
        stars(input, input, input); // 재귀함수 호출
 
        //출력
        for(String[]bb: str){
            for(String sss : bb){
                bw.write(sss);
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
    public static void stars(int low, int col, int size){
        if(size == 1) {
            str[low-1][col-1] = "*";
            return;
        }
    
        size /= 3; //간격으로 활용
 
        // 9번 재귀호출, 가운데 제외
        for(int i = low; low - size * 2 <= i; i -= size){
            for(int j = col; col - size * 2 <= j; j -= size){ 
                if(i == low - size && j == col - size) // 가운데 부분
                    continue;
                stars(i, j, size);
            }
        }
    }
}