#2447 : 별 찍기 - 10

풀이방법

사용된 것:

분할 정복

재귀

 

2022.05.18

분할 정복 문제이고, 재귀적으로 정의된 함수를 사용한다.

 

사용된 전역변수는 

char[][] print : 출력할 별 그림

이렇게 하나이다.

 

사용된 함수 star()의 구조를 간단히 설명하자면 다음과 같다.

 

함수 star()

개요

star()은 특정 영역에 대하여,

영역의 한 변의 길이가 3이라면 해당 영역에 3x3짜리 별 그림을 직접 찍고,

영역의 한 변의 길이가 3보다 크다면 재귀를 수행하는 함수이다.

 

매개변수

• int row : star()에서 다룰 영역의 시작부분(가장 왼쪽 위 지점)의 열 좌표
• int col : star()에서 다룰 영역의 시작부분(가장 왼쪽 위 지점)의 행 좌표
• int len : star()에서 다룰 영역의 한 변의 길이

 

작동방식

len이 몇인지부터 확인한다.

 

len이 3이라면 주어진 영역의 값을 다음과 같이 바꾼다:

주어진 영역의 1행: 별, 별, 별

주어진 영역의 2행: 별, 공백, 별

주어진 영역의 3행: 별, 별, 별

 

len이 3보다 크다면 다음과 같이 한다:

주어진 영역을 다음과 같이 (len/3)x(len/3)크기의 부분 영역 9개로 쪼개서

가운데 영역은 공백으로 채우고, 나머지 영역에 대해서는 재귀를 한다.

재귀	재귀	재귀
재귀	공백으로 채우기	재귀
재귀	재귀	재귀

 

코드

Java(2022.05.18)

import java.util.Scanner;

public class Main {
	
	static char[][] print;	//화면에 출력할 별들
	
	public static void star(int row, int col, int len) {
		
		//base case
		if(len == 3) {
			//첫째줄 (별 별 별)
			print[row][col] = '*';
			print[row][col+1] = '*';
			print[row][col+2] = '*';
			//둘째줄 (별 공백 별)
			print[row+1][col] = '*';
			print[row+1][col+1] = ' ';
			print[row+1][col+2] = '*';
			//셋째줄 (별 별 별)
			print[row+2][col] = '*';
			print[row+2][col+1] = '*';
			print[row+2][col+2] = '*';
		}
		
		//나머지 case
		else {
			int next = len/3;
			
			//첫째줄 (재귀 재귀 재귀)
			star(row, col, next);
			star(row, col+next, next);
			star(row, col+next+next, next);
			
			//둘째줄 (재귀 공백 재귀)
			star(row+next, col, next);
			for(int i = row+next; i<row+next+next; i++) {
				for(int j = col+next; j<col+next+next; j++) {
					print[i][j] = ' ';
				}
			}
			star(row+next, col+next+next, next);			
			
			//셋째줄 (재귀 재귀 재귀)
			star(row+next+next, col, next);
			star(row+next+next, col+next, next);
			star(row+next+next, col+next+next, next);
		}
		
		return;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		//N의 값 읽어오기
		int n = sc.nextInt();
		//별 그림 배열 생성
		print = new char[n][n];
		//별 그림 그리기
		star(0, 0, n);
		//별 그림 출력
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) sb.append(print[i][j]);
			sb.append(System.lineSeparator());
		}
		
		System.out.print(sb);
		
		sc.close();
	}

}