[JavaScript/BFS] 백준 골드 4 : 14226 - 이모티콘

https://www.acmicpc.net/problem/14226

14226번: 이모티콘

---

📌 작성한 코드 

// 14226
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim();

const N = Number(input);

// 1. 전체 복사 (일부만 복사하기 불가능)
// 2. 모두 붙여넣기(클립보드에 이모티콘이 있는 경우에만)
// 3. 화면에 있는 이모티콘 중 하나 삭제하기

// 목표 : 이모티콘 1개를 S개로 만드는 방법

const visited = Array.from({ length: N + 1 }, () => new Array(N + 1).fill(false));

const bfs = () => {
    const queue = [];
    queue.push([1, 0, 0]); // 개수, 시간, 클립보드

    let idx = 0;
    while (queue.length > idx) {
        const [count, time, clipboard] = queue[idx++];

        if (count <= 0 || count > N) continue;

        if (!visited[count][count]) {
            queue.push([count, time + 1, count]);
            visited[count][count] = true;
        }

        if (clipboard !== 0 && count + clipboard <= N && !visited[count + clipboard][clipboard]) {
            queue.push([count + clipboard, time + 1, clipboard]);
            visited[count + clipboard][clipboard] = true;

            if (count + clipboard === N) return time + 1;
        }

        if (!visited[count - 1][clipboard]) {
            queue.push([count - 1, time + 1, clipboard]);
            visited[count - 1][clipboard] = true;

            if (count - 1 === N) return time + 1;
        }
    }
};

console.log(bfs());

 

📌 설명 

이모티콘 1개에서 (복사, 붙여넣기, 1개 삭제) 3가지의 행동을 통해 S개의 이모티콘을 만들려고 한다. 이 때 S를 만드는 최소 시간을 구하는 문제이다. 

 

bfs를 이용해서 가능한 모든 경로를 시도해보고, visited 배열을 사용하여 이전에 이미 계산한 적 있는 연산은 제외해서 중복을 거른다.

- visited[count][clipboard] : count개의 이모티콘이 화면에 있고, 클립보드에 clipboard개의 이모티콘이 있는 상황이 사용된 적 있는지

- 1. 복사하기 : 클립보드에 현재 이모티콘 전체를 복사. 단, 이미 사용된 적 있으면 연산하지 않음

- 2. 붙여넣기 : 클립보드에 있는 이모티콘을 화면에 붙여넣기. 단, 클립보드가 비어있지 않고 / 연산되지 않았으며 / 붙여넣은 값이 S를 넘지 않을 때만 연산

- 3. 한 칸 삭제하기 : 화면에 있는 이모티콘을 한 칸 삭제하기. 단, 사용된 적 있으면 연산하지 않음

 

✅ 성공