[백준] 2448 별 찍기 - 재귀 JAVA

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

2448번: 별 찍기 - 11

코드설명

재귀를 활용하는 문제입니다.

   *                       
  * *                      
 *****

위의 삼각형을 재귀로 돌면서 찾아냅니다.

 

예로들면,

simulate(0, 24-1, 24) 로 재귀가 시작됩니다. 

 

그 이후에 함수호출을 살펴보면,

simulate(0,23,24)
simulate(0,23,12)
simulate(0,23,6)
simulate(0,23,3)

이 호출됩니다. 

                       *                       
                      * *                      
                     *****

 

simulate(3,20,3)

                       *                       
                      * *                      
                     *****                     
                    *                          
                   * *                         
                  *****

 

 

simulate(3,26,3)

                       *                       
                      * *                      
                     *****                     
                    *     *                    
                   * *   * *                   
                  ***** *****

 

simulate(6,17,6) --> 이제 simulate(r + size/2, c-size/2, size/2)가 분기되어 나와서 한번 실행됩니다.
simulate(6,17,3)

                       *                       
                      * *                      
                     *****                     
                    *     *                    
                   * *   * *                   
                  ***** *****                  
                 *                             
                * *                            
               *****

 

simulate(9,14,3)

                       *                       
                      * *                      
                     *****                     
                    *     *                    
                   * *   * *                   
                  ***** *****                  
                 *                             
                * *                            
               *****                           
              *                                
             * *                               
            *****

 

simulate(9,20,3)

                       *                       
                      * *                      
                     *****                     
                    *     *                    
                   * *   * *                   
                  ***** *****                  
                 *                             
                * *                            
               *****                           
              *     *                          
             * *   * *                         
            ***** *****

 

simulate(6,29,6) --> simulate(r + size/2, c + size/2, size/2); 가 분기되어 나와서 실행됩니다.
simulate(6,29,3) 

 

... 생략

 

simulate(12,11,12) --> simulate(r + size/2, c - size/2, size/2); 가 분기되어 나와서 실행됩니다.
simulate(12,11,6)  
simulate(12,11,3)

 

위와 같이 재귀가 모든 경우를 돌면서 실행됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N;
	public static int answer = 0;
	public static char[][] map;
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new char[N][2*N-1];
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<2*N - 1; j++) {
    			map[i][j] = ' ';
    		}
    	}
    	
    	//위에서부터 그려나갑니다.
    	simulate(0, N-1, N);
    	
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<2*N-1;j++) {
    			sb.append(map[i][j]);
    		}
    		sb.append('\n');
    	}
    	System.out.println(sb);
    }
    
    public static void simulate(int r, int c, int size) {
    	if( size == 3 ) {
    		
    		map[r][c] = '*';
    		map[r+1][c-1] = '*'; map[r+1][c+1] = '*';
    		map[r+2][c-2] = '*'; map[r+2][c-1] = '*'; map[r+2][c] = '*'; map[r+2][c+1] = '*'; map[r+2][c+2] = '*';
    		
    		return ;
    	}

    	
    	simulate(r, c, size/2); //위 삼각형
    	simulate(r + size/2, c - size/2, size/2); //좌 하 삼각형
    	simulate(r + size/2, c + size/2, size/2); //우 하 삼각형
    		
    }
}