[Algorithm] 백준 2447번 별 찍기 - 10 Node.js Javascript

 

 

 

문제 링크

• https://www.acmicpc.net/problem/2447

 

문제

 

재귀적인 패턴으로 별을 찍어보는 재귀 알고리즘 문제다. 3의 거듭제곱인 N이 주어지고 N x N으로 이뤄진 정사각형 안에서 특정 조건을 만족하는 별을 찍게 된다. 크기 3의 패턴은 가운데 공백이 존재하고, 가운데를 제외한 모든 영역에 별을 찍게 된다.

 

N이 3보다 큰 경우 정사각형의 패턴은 가운데 공백으로 채워진 (N/3) x (N/3) 정사각형을 (N/3) 크기의 정사각형 패턴으로 둘러싼 형태가 된다. 

 

예를 들어 N=3인경우

***
* *
***

 

N=9인 경우

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

 

N=27인 경우

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

 

입력

입력값은 3의 거듭제곱인 N이 주어진다. 정수 k에 대해 N은  N=3^k 가 된다. (1<= k <= 8)

 

풀이

 

재귀 알고리즘을 푸는데 이렇게 오래 시간이 걸린건 처음이다. 심지어 몇시간을 고민해도 문제를 풀지 못해서 구글링을 참고해서 Node.js 형태로 코드를 작성했다.

코드 Reference

• https://st-lab.tistory.com/95

 

위의 블럭을 배열로 생각한다면 N=3인 경우 모든 곳에 별이 삽입되고, (1,1) 영역에 공백이 들어가게 된다. N=9, N=27인 경우도 마찬가지 로직이 적용된다. 이를 재귀로 풀기 위해서는 공백인 구간의 조건을 만족하는 경우 공백으로 채우고, 공백 조건을 만족하지 못하는 경우 재귀 함수를 호출하게 된다.

 

만약 N=27인 경우에서 생각해보면 먼저 블록을 9개로 분리하고, 공백의 조건을 만족하면 공백으로 두고, 공백 조건을 충족하지 못하면 재귀함수를 호출하면서 N=9인 경우를 생각한다. 또 공백 조건이면 공백으로 두고, 아닌경우 재귀 함수를 호출해서 N=3인 경우를 생각한다. 

 

가장 복잡한 단계에서 가장 간단한 단계 까지 재귀 함수를 호출하면서 답을 찾아나간다. 재귀 알고리즘은 가장 마지막 단계를 기초로 전체 문제를 풀어가는 방식이다. 이를 분할 정복 알고리즘이라고 한다. 

 

코드

 

/*
    문제 : 별 찍기-10
    날짜 : 2022-06-04
    작성 : About-Tech
*/

const readline = require('readline');
const { stdin : input, stdout : output } = require('process');

const rl = readline.createInterface({input, output});

rl.on('line', (line)=>{
    const N = line.split(' ').map(e=>parseInt(e)).shift();
    const arr = new Array(N).fill(0).map(item=>(new Array(N).fill(0)))

    const star = (x, y, N, blank) => {

        // 공백인 경우
        if(blank){
            for(let i=x; i<x + N; i++){
                for(let j=y; j<y+N; j++){
                    arr[i][j] = ' ';
                }
            }
            return;
        }

        // 데이터를 더이상 쪼갤 수 없는 블록인 경우
        if(N === 1) {
            arr[x][y] = '*';
            return;
        }

        let size = N / 3;
        let count = 0;

        for(let i=x; i<x + N; i += size){
            for(let j=y; j < y + N; j += size){
                count++;
                
                // (1,1)의 영역은 배열의 5번째다.
                if(count == 5){
                    star(i, j, size, true);
                }else{
                    star(i, j, size, false);
                }
            }
        }

    }

    star(0, 0, N, false);

    let w = '';

    for(let i=0; i<arr.length; i++){
        for(let j=0; j<arr[i].length; j++){
            w += arr[i][j];
        }
        w += ('\n');
    }
    console.log(w);

    rl.close();
})

rl.on('close', ()=>{
    process.exit();
})

 

주의할 점은 2차원 배열을 두개의 반복문을 중첩해서 출력할 경우 백준에서 시간초과가 발생한다. 문자열로 변경한 후 출력해줘야 정답처리가 된다.

 

 

 

[Algorithm] 백준 10818번 최소 최대 문제 Node.js 여러줄 입력 받기

 

[Algorithm] Binary Search 알고리즘 Javascript (반복, 재귀, 트리구조)

 

[Algorithm] 분할정복 거듭제곱 분할제곱 알고리즘 Javascript