[java 백준] 실버 1/별찍기 -10

 

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

2447번: 별 찍기 - 10

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static int n;
    public static int m;
    public static char[][] arr;
 
    public static StringBuilder sb = new StringBuilder();
 
    // 공백을 출력하는 경우는 나머지가 1일때
    public static void Print(int row, int col, int num) {
        if (num == 1) {
            arr[row][col] = '*';// 재귀끝 별 그리기
            return;
        }
        int n = num / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == 1 && j == 1) {
                    continue;// 가운데를 공백으로 맞춰주기 위함
                }
                Print(row + (i * n), col + (j * n), n);
            }
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        // 우선 다 공백으로 채워놓기
        arr = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = ' ';
            }
 
        }
 
        Print(0, 0, n);
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(arr[i][j]);
            }
            sb.append('\n');
        }
        System.out.println(sb.toString());
 
    }
 
}

 

3으로 분할하는 것 까진 알겠는데 가운데를 공백을 만들어서 재귀 호출하는 아이디어를 도저히 모르겠었다.

내가 쓴 코드로 코딩하면 자꾸 별들이 이상하게 찍혀서 결국 도움을 받았다.

 

기존에 분할정복을 하는 코드들과 비슷한데, 가운데에 공백을 어떻게 만들어줄지를 생각해야했다.

그러기 위해선 차라리 전체 공간을 다 공백으로 채우고 -> 가운데부분만 빼고 별을 찍어주는 것이 더 효율적이였다.

 

기본 패턴은

이런 모양인데 이걸 기존의 분할정복 코드로 구현해보면

 

행이 3개이고 열도 3개이기 때문에 

for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
        Print(row+(i*div),col+(j*div),num);
    }
}

이렇게 생각해줄 수 있다.

 

자 그러면 예제에서 주어진 27을 기준으로 얘가 저 디폴트모양이 될때까지 과정을 가시화 시켜보겠다.

 

n이 3의 제곱수이기 때문에 3으로 나누면서 분할을 할거다

그럼 처음에는 9등분이 이런식으로 된다.

이걸 앞서 말했던 분할정복 코드에 가운데 공백을 설정해주면

for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
       if(i==1&&j==1){//둘다 1일때가 가운데임
            continue; //이 if문만 탈출하고 다시 반복문으로 올라가기
        }
        Print(row+(i*num/3),col+(j*num/3),num/3);
    }
}

 

그리고 이걸 (행,열,num)으로 나타내보면 

9를 다시 분할하면 num은 3이 되는데 이번에는 (0,0,9) 부분만 자세히 보겠다.

 

num이 3일때는 위 사진처럼 쪼개진다. 하지만 여기서 

이 모양을 기준으로 한번 더 쪼갤 수 있다. 

이번에도 가장 위에 있는 (0,0,3)만 볼거고 얘를 한번더 쪼개볼 것이다. num/3=1이 되게끔!

 

이제 쪼갤 수 있는 만큼 다 쪼갰다. 

 

그래서 다 쪼갰으면 진짜 별을 그려줘야하기 때문에

 

if(num==1){
    arr[row][col]='*';
   continue; //return써야 뒷구문 실행안됨. //num이 1일때는 더이상 쪼갤 수 없기에 num/3하는 과정이 필요없기 때문//그렇기에 return써서 Print함수 탈출
}

이렇게 구현해볼 수 있다.

 

가운데 공백이 걱정될 수도 있는데 어차피 if(i==1&&j==1) continue;를 통해 Print함수 호출조차 해주지 않아서 걱정할 필요없다. 

 

 

 

*중요한것은*

 

i=1,j=1일때는 가운데이기 때문에 공백유지를 위해 continue 예약어 사용

num==1일때는 쪼갤만큼 다 쪼갰기 때문에 별을 출력해야함. 

 

참고자료

https://fbtmdwhd33.tistory.com/21

[백준,BOJ 2447] 별 찍기-10(JAVA 구현)