백준 2447번 - 재귀함수 별찍기

착안점 : 크기가 3인 패턴이 기본 패턴이 되고, 숫자가 커지면 하위 패턴이 기본 패턴의 별 하나가 된다. 즉, 크기가 9라면 크기가 3인 기본 패턴에서 별 하나가 크기가 3인 3X3 패턴전체가 된다.

 

알고리즘 : 재귀함수를 이용해서 배열에 배열의 순서가 아닌 패턴에 맞게 별을 넣는다. 배열을 출력하면 위와 같이 출력되지만 실제로는 배열에 별이 입력되는 순서는 arr[0][0]에서 시작하여 크기 3인 기본패턴이 입력된 후 arr[3][0]에서부터 또 기본패턴이 입력된다. 즉, 시작점을 옮기면서 기본패턴을 하나씩 입력해 나가는 것이다.

 

정답코드

import java.util.*;

public class Main {
	static char arr[][];	//메인과 Star 함수 모두에서 사용하기 위해 static 변수로 선언

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();	// 크기 N을 받아옴
		arr = new char[N][N];	// 크기가 NXN인 배열 생성
		
		for(int i=0; i<arr.length;i++) {
			Arrays.fill(arr[i], ' ');	// 배열의 모든 값을 ' '(공백)으로 초기화
		}
		
		Star(0,0,N);	// 별 찍기 함수 불러오기
		
		for(int i=0;i<arr.length;i++) {
			System.out.println(arr[i]);
		}
		
	}
	
	public static void Star(int a, int b, int N) {	// 시작점 a,b와 크기 N을 받아옴
		int d = N/3;	// 크기를 3으로 계속 나누어 1이 되게 하여 별을 찍음
		
		if(N==1) {
			arr[a][b] = '*';	// N=1 일 때 해당 배열 위치에 별을 찍음
			return;
		}
		
		for(int i=0;i<3;i++) {		// 기본 패턴의 크기가 3X3이므로 for문도 3x3으로 돌아감
			for(int j=0;j<3;j++) {
				if(i==1&&j==1) continue;	// 가운데 값에는 별을 찍지 않으므로 넘어감
				Star(a+(d*i),b+(d*j),d);	// 시작점을 옮기면서 기본 패턴을 찍음
			}
		}		
	}
}

- N이 3의 거듭제곱이므로 3으로 계속 나누어 N=1이 되게하여 기본 패턴을 찍는다.

- 그리고 시작점을 N/3 만큼씩 옮겨 기본 패턴을 계속 찍어나간다.

- 크기가 9라면 arr[0][0]에서 시작하여 arr[2][2]까지 기본패턴을 찍은 후 9/3=3 만큼 시작점을 옮겨 arr[0][3]에서 시작하    여 arr[2][5]까지 기본 패턴을 찍는 식이다. 즉, 배열의 순서가 아닌 기본 패턴에 맞는 순서대로 별을 찍어 나간다.

- 만약, 크기가 27이 되면 위에서 설명한 크기가 9일 때의 경우를 실행한 후 27/3=9 만큼 시작점을 옮겨 또 크기가 9인    패턴을 찍어나가는 식이다.