[백준] 13549번: 숨바꼭질 3 - Node.js (자바스크립트)

1. 문제 ㅡ 13549번: 숨바꼭질 3 (난이도: Gold V)

13549번: 숨바꼭질 3

2. 풀이 ㅡ Node.js (자바스크립트)

const [subin, sister] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(val => +val);
const visited = Array.from({ length: 100001 }, () => false);

// 수빈의 현재 위치(N)을 기준으로 BFS 탐색
const moveSubin = N => {
  const queue = [[N, 0]];
  visited[N] = true;

  while (queue.length) {
    const [current, time] = queue.shift();

    if (current === sister) return time;
	
    // 이동 가능한 경로: 위치 + 1, 위치 - 1, or 위치 * 2
    [current - 1, current + 1, current * 2].forEach(move => {
      if (visited[move] || move < 0 || move > 100001) return;

      visited[move] = true;

	  // 위치 * 2, 즉 순간이동한 경우 시간이 증가하지 않으므로 time + 1 해주지 않음 
      // 순간이동 한 경우를 먼저 확인해야 하기 때문에 unshift 사용해서 queue 앞으로 넣어줌 
      if (move !== current * 2) queue.push([move, time + 1]);
      else queue.unshift([move, time]);
    });
  }
};

console.log(moveSubin(subin));

 

2-1. 풀이 설명

기존에 풀어봤던 숨바꼭질 문제의 응용 버전이다. 문제의 핵심은 순간이동(위치 * 2) 할 때는 시간이 증가하지 않는다는 점이다. 즉, 수빈의 다음 위치(move)를 확인하는 과정에 우선순위가 고려되어야 한다. 

 

우선순위를 반영하기 위해 데크 자료구조를 사용했다. 만약 수빈이 이동할 수 있는 거리가 순간이동한 거리라면 queue의 가장 앞으로 넣기 위해 unshift 메서드를 사용했고, 순간이동 시 시간이 지나지 않으므로 time + 1 대신 그냥 현재 time 정보를 그대로 다시 넣어줬다. 반대로 순간이동이 아니라 앞뒤로 한 칸 이동한 경우에는 time + 1을 해준 후 queue에 push 해주었다.  

 

2-2. 회고

• 첫 골드 레벨 문제 풀이 완료!