백준 알고리즘 2447번 별 찍기 10 JAVA

 

 

백준 알고리즘 2447번은 별을 출력하는 문제다. 3의 제곱으로 만들어진 입력값을 받아서 중간이 비어있는 2차 배열을 만들어내야 한다. 입력값은 3, 9, 27 순서로 증가하게 되고, 그에 따라 그래프의 모양이 변하지만 팩토리얼 형식으로 출력된다.

 

백준 알고리즘 2447번 문제 해결은 재귀함수를 사용하는 것이다. 재귀함수를 통해서 반복 연산을 하기 위해서는 3가지 조건이 필요하다.

 

1. 탈출전략

2. 재귀 조건 변경

3. 초기 재귀 시작 조건

 

 

백준 알고리즘 2447번 문제의 경우 탈출전략을 세우기 위해서 입력값 N을 반복해서 쪼개는 작업을 진행해야 한다. N은 자연수 k에 대해 3의 거듭제곱이기 때문에 3으로 반복적으로 나눠줄 경우 최종적으로 1에 수렴하게 된다. 1이 되면 별을 찍고 탈출하게 된다.

 

재귀 조건은 두가지로 분기된다. 출력 그래프의 값은 '*'과 공백으로 구분된다.  입력값 3에 대해서  (0,0) (0,1) (0,2) (1,0) (1,1) 순서로 진행되게 되며 (1,1)의 순서에서 공백이 출력된다. 입력값 9는 입력값 3의 그래프가 반복되는 것이고 입력값 27도 마찬가지기 때문에 재귀를 돌면서 5번째의 경우 공백을 출력할 것인지, 별을 찍을 것인지에 대한 조건을 달아줘야 한다.

 

마지막으로 초기 재귀조건을 설정해야 한다. 그래프는 0,0부터 시작하게 되고, 입력값 N을 받아야 하며 제일 처음 찍혀야 하는 문자는 별표다. recur(0,0,N,false)에서 프로그램은 시작한다.

백준 알고리즘 2447번

백준 알고리즘 2447번

 

JAVA 코드

import java.util.Scanner;
 
public class A_2447 {

    // '*' 혹은 공백이 들어갈 2차원 배열을 선언한다.
	static char[][] starCode;
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
 
		starCode = new char[N][N];
        
        // 재귀함수 시작은 0,0에서 부터 시작한다.
		recur(0, 0, N, false);
 

        // 백준 코드에서는 시간초과 문제로 StringBuilder를 사용한다.
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sb.append(starCode[i][j]);
			}
			sb.append('\n');
		}
		System.out.print(sb);
	}
 
	static void recur(int x, int y, int N, boolean blank) {
 
		// (0,0)(0,1)(0,2)(1,0) 후 5번째는 반드시 공백이다.
		if (blank) {
			for (int i = x; i < x + N; i++) {
				for (int j = y; j < y + N; j++) {
					starCode[i][j] = ' ';
				}
			}
			return;
		}
 
        /*
		재귀 탈출 조건을 만들어준다.
        3의 제곱으로 입력받은 수를 계속 쪼개서 1이 되는 조건을 만든다.
         */
		if (N == 1) {
			starCode[x][y] = '*';
			return;
		}
 
        /*
            blockSize는 3으로 쪼개면서 1이 될때 까지 반복한다.
            재귀함수가 돌면서 count를 세고, 카운트가 5가 될 때마다 공백을 처리한다.
        */
		int blockSize = N/3;
		int count = 0;
		for (int i = x; i<x+N; i+= blockSize) {
			for (int j = y; j<y+N; j+= blockSize) {
				count++;
				if (count == 5){ 
					recur(i, j, blockSize, true);
				} else {
					recur(i, j, blockSize, false);
				}
			}
		}
	}
}

 

백준 알고리즘 2447번은 재귀함수를 이용하는 것이다. 재귀함수를 머리로만 생각하면 답이 안나온다. 손으로 그림을 그리면서 순서도가 어떻게 진행되는지 먼저 생각해보는게 도움이 많이 된다. 함수가 반복되면서 탈출전략과 재귀 하는경우 변수의 변경등을 신경쓰면 답을 도출해낼 수 있다.