[BFS: 상태트리탐색]송아지 찾기

문제

현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.

 

현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

 

송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

 

문제풀이

이진 트리 너비 탐색

 

이때 중요한 점은 한번 방문했던 지점은 더 이상 참조 및 순회하지 않음으로써 시간 복잡도를 줄이는 것이다.

최단 경로를 구하기 위해서는 다음과 같이 각 지점에 대한 거리를 거리의 정보를 저장하고 있는 배열에 저장하였다.

 

거리 정보를 저장

 

코드

function solution(s, e) {
  let answer = 0;
  let queue = [];
  let ch = Array.from({length: 10001}, () => 0);
  let dis = Array.from({length: 10001}, () => 0);
  queue.push(s);
  ch[s] = 1; //지점의 중복을 방지
  dis[s] = 0; //출발 지점의 거리를 0으로 초기화
  while(queue.length) {
    let v = queue.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;
          queue.push(nv);
          dis[nv] = dis[v] + 1; //다음 지점의 거리는 현재 지점에서의 거리에 1을 가산
      }
    }
  }
}

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

---

function solution(s, e) {
  let answer = 0;
  let queue = [];
  let ch = Array.from({length: 10001}, () => 0);
  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++; //레벨을 모두 순회한 뒤 다음 레벨로 가기 전에 레벨 값 가산
  }
}

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