BFS - 송아지 찾기

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음 과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요.

 

▣ 입력설명

첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.

 

▣ 출력설명

점프의 최소횟수를 구한다. 답은 1이상입니다.

 

▣ 입력예제 1

5 14

 

▣ 출력예제 1

3

 

▣ 입력예제 2

8 3

 

▣ 출력예제 2

5

---

🚀BFS로 접근하기

현수가 현재 위치에서 접근할 수 있는 지점을 트리 형태의 자료구조로 표현할 수 있다.

송아지의 위치 E 노드까지의 최단거리를 구하면 된다.

 

BFS로 어떻게 접근해야되는지 고민이 많이 되었다. 이렇게 트리구조를 그려서 접근할 수 있는지는 꿈에도 몰랐다.

비슷한 문제를 만나면 꼭 기억하고 있다가 이렇게 접근해봐야겠다.

 

let [s, e] = require('fs').readFileSync('input.txt').toString().trim().split(' ').map(Number);
let visited = Array.from({ length: 10001 }).fill(0);

function bfs(here) {
  const queue = [];
  visited[here] = 1;
  queue.push(here);
  while (queue.length) {
    const elem = queue[0];
    if (elem === e) return;
    queue.shift();
    if (!visited[elem - 1]) visited[elem - 1] = visited[elem] + 1;
    if (!visited[elem + 1]) visited[elem + 1] = visited[elem] + 1;
    if (!visited[elem + 5]) visited[elem + 5] = visited[elem] + 1;
    queue.push(elem - 1);
    queue.push(elem + 1);
    queue.push(elem + 5);
  }
}

function solution() {
  bfs(s);
  return visited[e] - 1;
}

console.log(solution());