[백준] 14226번 이모티콘 - Node.js

 

문제

 

---

문제 풀이

 해당 문제는 3가지 진행 방식으로 진행하여 원하는 개수의 이모티콘을 만드는 최소의 방법을 구하는 문제이다. 최소의 방법을 구하기 위해 BFS를 사용하였다. 

 

 3가지의 진행 방식을 아래와 같이 오브젝트로 생성하였다. count는 현재 이모티콘의 길이, x는 클립보드의 저장된 이모티콘의 길이이다.

const actionCase = {
        copy (count ,x){
            return [count ,count]
        },
        paste (count ,x){
            return [count + x, x]
        },
        deleteOne (count,x){
            return [count-1,x]
        }
    }

 

해당 진행 방식으로 BFS로 진행하면 된다. 하지만 일반적인 BFS문제와 다른 점이 있다. 그것은 클립보드이다.

일반적인 BFS문제는 visited를 배열로 저장하여 중복을 해소한다. 하지만 해당 문제는 클립보드로 인하여 같은 count를 가지더라고 다른 접근 방식을 가질 수 있기 때문이다.

 

ex ) 현재 길이가 4이고 클립보드의 길이가 1인 경우 !== 현재 길이가 4이고 클립보드 길이가 3인 경우

 

그렇기에 visited를 2차원 배열로 만들어 클립보드를 추가적인 경우의 수로 지정해준다.

 

풀이 코드

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`4`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

function solution(){
    const target = Number(input());
    let visited = Array.from({length : 2000}, ()=>Array(1000).fill(0));
    let queue = [[1,0,0]];
    visited[1][0] = 1;

    const actionCase = {
        copy (count ,x){
            return [count ,count]
        },
        paste (count ,x){
            return [count + x, x]
        },
        deleteOne (count,x){
            return [count-1,x]
        }
    }

    while(queue.length){
        const [count,clip,time] = queue.shift();
        if(count === target){
            console.log(time);
            break;
        }
        for( action of ['copy','paste', 'deleteOne']){
            const NextPos = actionCase[action](count,clip);
            if( NextPos[0] > 0 && NextPos[0] < 2000 && !visited[NextPos[0]][NextPos[1]]){
                visited[NextPos[0]][NextPos[1]] = 1;
                queue.push([...NextPos,time+1])
            }
        }
    }
}

solution();

 

 

 

 ** 해당 문제는 이전 숨바꼭질 문제와 비슷한 유형의 문제이다. 참고하면 더욱 좋을 것 같다.