[백준] 14226 이모티콘 - JavaScript(NodeJS)

문제

14226번: 이모티콘

 

풀이

처음 시작은 이모티콘 1개로 시작한다.

다음 3가지 연산으로 이모티콘을 S개로 만들면 된다.

 

모든 연산은 1초가 걸린다.

1. 화면의 이모티콘을 모두 복사해서 클립보드에 저장
2. 클립보드에 있는 이모티콘을 모두 화면에 붙여넣기
3. 화면의 이모티콘 중 한 개 삭제

 

 

클립보드에 대한 조건은 다음과 같다.

 

클립보드에 이모티콘을 복사하면, 이전 클립보드가 덮어씌워진다.
클립보드가 비었다면, 2번 명령 붙여넣기 불가능.

 

풀이 방향

처음에는 이모티콘 1개로 시작해야 하며, 3가지 연산의 경우를 BFS로 탐색한다.

 

탐색하면서 클립보드의 처리가 가장 중요한데, 클립보드는 위와 같은 조건이 있었다.

 

클립보드에 대한 조건으로 미루어 보면,

 

1. 각 노드(경우)마다 가지고 있는 클립보드가 존재해야 한다.
2. 이전에는 동일한 노드로의 중복을 허락하지 않았지만, 해당 문제에서는 동일한 노드로의 방문도 가능하다.
3. 하지만, 동일한 노드에서 동일한 클립보드를 가지는 경우의 수는 줄여줘야 한다.

 

클립보드는 노드마다 개별 값들을 가져야 하므로, 노드의 이동과 함께 큐에 같이 개별 값으로서 push한다.
방문 배열을 선언해야 하는데, 방문 배열은 동일한 갯수인지와 동일한 클립보드를 가지는지를 모두 고려해야 한다.
즉, 방문 배열은 2차원으로 선언한다.

이모티콘 갯수가 S일 때 클립보드 또한 S의 값을 가질 수 있으므로 1000x1000 크기로 선언한다.

 

BFS 내 while 루프에서 1번 연산, 2번 연산, 3번 연산을 각각 실행해준다.
만약 현재 이모티콘 갯수가 S라면 재귀를 탈출하면서 시간을 출력하면 된다.

 

간단하게 그림으로 나타내면 다음과 같다.

 

추가적으로 유의할 사항은,

 

1. 클립보드에 이모티콘이 이미 존재해도, 현재 화면에 있는 이모티콘들을 복사해서 덮어 씌워줄 수 있다.
2. 클립보드에서 이모티콘을 가져와 붙여넣기를 한다고 하더라도, 클립보드에 저장되어 있던 이모티콘들은 삭제되지 않는다.
즉, 클립보드가 처음의 0개 상태가 아니라면, 다음 노드에서 또 붙여넣기를 실행할 수 있다.

 

이를 고려해서 코드를 작성해보자.

 

 

 

코드

const sol = (S) => {
  const MAX_SIZE = 1000;
  const check = Array.from({ length: MAX_SIZE + 1 }, () => Array(MAX_SIZE + 1).fill(0));
    // check배열은 2차원이면서 (next, clipBoard) 값을 가지므로 최대 (S,S) = (1000,1000) 크기까지 고려해야 한다.

  function bfs() {
    const queue = [];
    queue.push([1, 0, 0]); // 큐에 [현재위치, 클립보드, 시간] 값을 넣어준다.
    check[1][0] = 1; // (현재위치 : 1, 클립보드 : 0)에 방문처리한다.

    while (queue.length) {
      const [now, clipBoard, time] = queue.shift(); // 큐이므로 shift 메서드를 사용하는 것에 유의한다.
      if (now === S) return time;
      if (0 >= now || now > MAX_SIZE) continue; // S의 범위는 2<=S<=1000을 가진다.

      if (!check[now][now]) { // 연산 1. 클립보드에 현재 화면의 이모티콘 수를 저장하기
        check[now][now] = 1;
        queue.push([now, now, time + 1]);
      } 

      if (clipBoard && now + clipBoard <= MAX_SIZE) { // 연산 2. 클립보드에 있는 이모티콘을 화면에 붙여넣기
        if (!check[now + clipBoard][clipBoard]) {
          check[now + clipBoard][clipBoard] = 1;
          queue.push([now + clipBoard, clipBoard, time + 1]);
        }
      }

      if (!check[now - 1][clipBoard]) { // 연산 3. 화면의 이모티콘 중 한 개 삭제하기
        check[now - 1][clipBoard] = 1;
        queue.push([now - 1, clipBoard, time + 1]);
      }
    }
  }

  return bfs();
};

// 백준에서 입력을 받는 코드
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    console.log(sol(+line));
  })
  .on("close", () => {
    process.exit();
  });