백준 14226 이모티콘

문제

제한 사항

입출력 예

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim();

const solution = (input) => {
  const end = +input;
  const visited = Array.from(Array(1001), () => Array(1001).fill(0));
  const bfs = (start) => {
    const queue = [];
    visited[start][0] = 1; // 방문 확인용
    queue.push([start, 0, 0]); // 시작점, 클립보드에 복사된 이모티콘 수, 소요된 시간
    while (queue.length) {
      const [cur, clipBoard, time] = queue.shift();
      if (cur == end) return time;
      if (cur <= 0 || cur > 1000) continue;

      if (!visited[cur][cur]) {
        // 클립 보드에 현재 이모티콘 수 저장
        visited[cur][cur] = 1;
        queue.push([cur, cur, time + 1]);
      }

      if (clipBoard && cur + clipBoard <= 1000) {
        // 클립보드에 저장 되어있는 이모티콘을 화면에 붙여넣기
        if (!visited[cur + clipBoard][clipBoard]) {
          visited[cur + clipBoard][clipBoard] = 1;
          queue.push([cur + clipBoard, clipBoard, time + 1]);
        }
      }

      if (!visited[cur - 1][clipBoard]) {
        // 화면에 이모티콘 하나 지우기
        visited[cur - 1][clipBoard] = 1;
        queue.push([cur - 1, clipBoard, time + 1]);
      }
    }
  };

  const time = bfs(1);
  return time;
};

console.log(solution(input));

• 클립보드의 처리가 중요하다.
• 클립보드와 노드 둘다 방문 처리를 해야한다. 따로 나눠서 만들지 않고 visited 배열을 2차원 배열로 선언했다.

복습

const sol = (end) => {
  // 이모티콘과 클립보드 사용여부를 check
  const vistited = Array.from(Array(1001), () => Array(1001).fill(0));

  const bfs = (start, end) => {
    const queue = [];
    vistited[start][0] = 1;

    // 시작이모티콘 수, 클립보드 이모티콘 수, time
    queue.push([start, 0, 0]);
    while (queue.length) {
      const [cur, clipBoard, time] = queue.shift();

      if (cur === end) return time;
      if (cur <= 0 || cur > 1000) continue;

      // 현재 이모티콘 수를 클립보드로 복사
      if (!vistited[cur][cur]) {
        vistited[cur][cur] = 1;
        queue.push([cur, cur, time + 1]);
      }

      // 클립보드에 저장된 이모티콘 화면에 붙여넣기
      if (clipBoard && cur + clipBoard <= 1000) {
        if (!vistited[cur + clipBoard][clipBoard]) {
          vistited[cur + clipBoard][clipBoard] = 1;
          queue.push([cur + clipBoard, clipBoard, time + 1]);
        }
      }

      // 화면 이모티콘 지우기

      if (!vistited[cur - 1][clipBoard]) {
        vistited[cur - 1][clipBoard] = 1;
        queue.push([cur - 1, clipBoard, time + 1]);
      }
    }
  };

  // 처음에 이모티콘 한개에서 end개수가 될 때까지 걸리는 시간
  const time = bfs(1, end);

  return time;
};