[JavaScript/section 9] 05 - 송아지 찾기

📌 05 - 송아지 찾기(BFS : 상대트리탐색)

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 문제이다.

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

📍 출력설명
점프의 최소횟수를 구한다. 답은 1 이상이다.

 

문제를 해석하면 현수의 위치(출발 지점)에서 송아지의 위치(도착지점)까지의 최단 거리를 구하는 문제이다. 즉, 두 노드 사이의 최단 경로를 구하는 문제이므로 넓이 우선 탐색(BFS)으로 탐색하는 것이 좋다. 

여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 깊이 우선 탐색(DFS)으로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, 넓이 우선 탐색(BFS)의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다.

 

📝 풀이 방법

이진트리 넓이우선탐색(BFS)의 과정을 먼저 이해하고 오면 좋다.

문제 풀이 방법에는 2가지가 있는데 두 번째 방법의 경우 트리의 레벨을 이용한 방법이다. 첫 번째 방법으로 이해를 한 후 두 번째 방법도 참고해서 보면 된다.

x - 현재 좌표, nx - 다음에 이동할 좌표, ch[x] - 현재 좌표에 오기까지 몇 번 움직였는지에 대한 값이 저장

• nx가 송아지의 좌표와 같다면 ch[x]에 + 1을 return 한다.
• nx가 송아지의 좌표와 같지 않다면 nx가 좌표에서 벗어나지 않는지, 이동한 적이 있는 좌표인지 확인한 후 조건에 적합하면 큐에 nx를 추가한다. (이동한 적이 있는 좌표로 이동하면 최단 경로가 아님)

// 현재 좌표에 오기까지 몇 번 움직였는지에 대한 값을 저장하는 방법
function solution(s, e) {
  let answer = 0;
  const queue = [];
  const ch = Array.from({ length: 10001 }, () => 0);
  queue.push(s);

  while (queue.length) {
    const x = queue.shift();

    for (let nx of [x - 1, x + 1, x + 5]) {
      if (nx === e) return ch[x] + 1;
      if (nx > 0 && nx <= 10000 && ch[nx] === 0) {
        queue.push(nx);
        ch[nx] = ch[x] + 1;
      }
    }
  }

  return answer;
}

console.log(solution(8, 3));

// 트리의 레벨을 이용한 방법
function solution(s, e) {
  let answer = 0;
  let ch = Array.from({ length: 10001 }, () => 0);
  let queue = [];
  queue.push(s);
  ch[s] = 1;

  let L = 0;
  while (queue.length) {
    let len = queue.length;

    for (let i = 0; i < len; i++) {
      let x = queue.shift();
      
      for (let nx of [x - 1, x + 1, x + 5]) {
        if (nx === e) return L + 1;
        if (nx > 0 && nx <= 10000 && ch[nx] === 0) {
          ch[nx] = 1;
          queue.push(nx);
        }
      }
    }
    L++;
  }
  return answer;
}

console.log(solution(5, 14));