[알고리즘/인프런] 송아지 찾기

문제

---

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

 

풀이

---

BFS는 큐를 이용한다.

BFS는 각 레벨을 모두 살펴보고 다음 레벨로 내려가는 레벨 탐색을 사용하기 때문에 출발점에서 도착지로 가는 최단 거리를 구할 때 사용한다. ⭐⭐⭐

레벨 탐색을 하게 되면 한 번만에 갈 수 있는 레벨의 정점을 모두 탐색한 후에 두 번만에 갈 수 있는 레벨의 정점들을 탐색하는 식으로 진행한다.

도착 지점에 도달했는지의 여부를 shift할 때가 아니라 다음 노드를 만들어서 넣을 때 확인하는 것이 효율적이다. 또 레벨을 이용한 풀이가 따로 dis 배열을 만들지 않아도 되기 때문에 메모리 측면에서 효율적이다.

 

#1 distance 배열 활용

function solution(s, e) {
  let q = [];
  let ch = Array.from({ length: 100001 }, () => 0); // 방문 확인
  let dis = Array.from({ length: 100001 }, () => 0); // 거리

  q.push(s);
  ch[s] = 1;
  dis[s] = 0;

  while (q.length) {
    const v = q.shift();

    for (let nv of [v + 1, v - 1, v + 5]) {
      if (nv === e) return dis[v] + 1; // 도착 지점
      if (nv > 0 && nv <= 10000 && ch[nv] === 0) {
        ch[nv] = 1;
        dis[nv] = dis[v] + 1;
        q.push(nv);
      }
    }
  }
}

 

#2 Level 활용

function solution(s, e) {
  let q = [];
  let ch = Array.from({ length: 10001 }, () => 0);

  // 출발지점
  q.push(s);
  ch[s] = 1;
  let L = 0;

  while (q.length) {
    const len = q.length;

    // 동일 레벨 vertex 순회
    for (let i = 0; i < len; i++) {
      const v = q.shift();

      for (let nv of [v + 1, v - 1, v + 5]) {
        if (nv === e) return L + 1; // 도착지점
        // 방문할 수 있는 경우
        if (nv > 0 && nv <= 10001 && ch[nv] === 0) {
          ch[nv] = 1;
          q.push(nv);
        }
      }
    }
    
    L++;
  }
}