[코딩테스트] Police chase - Queue (JavaScript)

문제

Police officer Daniel has been informed of the location of a suspect and wants to catch him immediately.

He starts at a point N on a number line and the suspect is at a point M on the same number line.

Police officer has two modes of transportation: walking and teleporting.

Walking: Police officer can move from any point X to the point X-1 or X+1 in a single minute.

Teleporting: Police officer can move from any point X to the point 2*X in a single minute.

If the suspect, unaware of its pursuit, does not move at all, how long does it take for Police Officer Daniel to catch him?

매개변수

• N : number Type (0 <= N <= 100,000)
• M : number Type (0 <= M <= 100,000)

아웃풋

• Number : the least amount of time, in minutes.

예시

const N = 11;
const M = 81;
const output = policeChase(N, M);
console.log(output); // 5

 

솔루션

queue에 [위치, depth] 배열을 엘리먼트로 담기

이동시킬 수 있는 모든 방법을 동시에 사용해서 (-1, +1, x2) 위치를 움직이기

완전 탐색으로 진행하여, 먼저 목표 위치에 도달하면 해당 depth를 리턴

 

function policeChase(N, M) {

  // 방문 기록 담을 배열 선언
  const visit = Array(100000).fill(0)

  // queue에 배열을 엘리먼트로 담기 [위치, depth]
  let queue = [[N, 0]]

  // queue 길이 0 이상이면 반복문 돌리기
  while(queue.length) {

    // queue의 왼쪽부터 비워주며 확인하기
    const [location, depth] = queue.shift();

    // 조회할 위치를 이미 방문했다면 continue, 방문하지 않았다면 visit 배열 요소 1 할당
    if (visit[location] === 1) continue;
    visit[location] = 1

    // 위치가 M이라면 depth를 리턴
    if (location === M) return depth

    // 위치를 이동시킨 뒤 다시 queue에 push 하기
    queue.push([location+1, depth+1])
    queue.push([location-1, depth+1])
    queue.push([location*2, depth+1])

  }
}