[백준] 2447번 - 별 찍기 - 10

 

2447번: 별 찍기 - 10

 

 

 

별 찍기 10이다. 재귀함수와 분할정복 알고리즘을 사용하여 해결할 수 있다.

 

분할정복에 익숙하지 않다면 아래 문제를 먼저 해결해보자.

[백준] 2630번 - 색종이 만들기

 

 

 

 

문제에서 주어진 조건인 N이 3의 거듭제곱이라는 것과 예제 출력을 토대로 문제 풀이 실마리를 찾을 수 있다. 예제 출력1을 보면 길이 27짜리 전체 구조는 길이가 9인 닮은 도형의 9구획으로 나눌 수 있다.

 

 

그리고 마찬가지로 길이가 9인 각 구획 역시 길이가 3인 작은 구획 9개로 이루어져 있다. 

 

별 도형의 한 변의 길이인 N이 3의 거듭 제곱이기 때문에 N은 언제나 3으로 나누어 떨어지고, 길이가 N인 도형을 길이가 N/3인 도형 9개로 연속해서 나눌 수 있으므로 전체 문제를 작은 부분으로 나누어 해결하는 분할 정복을 이용할 수 있다. 

 

그렇다면 분할 정복을 사용하기 위한 재귀함수는 어떻게 구현해야 할까?

 

출력해야 하는 별 모양을 담는 boolean[][] map 배열을 선언한다. 최종적으로 출력할 때에는 map[i][j] 자리에 별을 출력하든지, 공백으로 남기든지 둘 중 하나이기 때문에 boolean을 사용하였다.

재귀 함수 makeStar 은 이중 방복문을 사용하여 9개의 작은 구획을 탐색하는데, 가운데에 공백이 있는 형태라는 문제 조건을 따라 5반복 때에는 별을 생성하지 않고 continue 시키고, 나머지 8구획에 대해서는 재귀호출을 하여 별을 생성할 수 있도록 한다. 이렇게 하기 위해서는 makeStar에 3개의 인자를 전달해 주어야 하는데, map상에서 탐색을 시작하는 행 번호(y), 열번호(x), 구획 한변의 길이(size)이다. size는 재귀호출을 할 때마다 size / 3 씩 감소한다.

size == 1 일때에는 별을 생성하고 재귀를 종료시킨다.

 

static void makeStar (int y, int x, int size) {
    
    // size == 1 이면 별을 생성하고 재귀 종료
    if (size == 1) {
        map[y][x] = true;
        return;
    }

    int ns = size/3;
    int cycle = 1;

    for (int i=y; i<y+size; i+=ns) { 
    // 행, 열에 대하여 현재 크기인 size만큼만 탐색을 한다. 
    // i와 j의 증가분을 i+=ns로 하여 현재 도형을 세로로 3등분, 가로로 3등분 총 9구획으로 나눌 수 있다.
    
        for (int j=x; j<x+size; j+=ns) {
			
            // 가운데 공백영역에 해당한다면 별 생성x
            if (cycle++ == 5) 
                continue;

            makeStar(i, j, ns);
        }
    }
}

 

 

 

 

 

 

 

 

전체 코드

import java.util.*;

public class Main {
    
    static final char star = '*';
    static final char space = ' ';
    static boolean[][] map;
    static int N;
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        
        map = new boolean[N][N];
        
        makeStar(0, 0, N);
        
        
        StringBuilder sb = new StringBuilder();
        
        for (boolean[] row : map) {
            for (boolean col : row) {
                
                if (col) 
                    sb.append(star);
                else 
                    sb.append(space);
            }
            sb.append("\n");
        }
        
        System.out.println(sb);
        
        sc.close();
    }
    
    static void makeStar (int y, int x, int size) {
        
        if (size == 1) {
            map[y][x] = true;
            return;
        }
        
        int ns = size/3;
        int cycle = 1;
        
        for (int i=y; i<y+size; i+=ns) {
            for (int j=x; j<x+size; j+=ns) {
                
                if (cycle++ == 5) 
                    continue;
                
                makeStar(i, j, ns);
            }
        }
    }
}