[JS] 코딩 테스트 문제 : 송아지 찾기 [BFS : 상태트리탐색]

문제 : 송아지 찾기(BFS : 상태트리탐색)

문제 설명

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

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

▣ 입력설명

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

▣ 출력설명

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

▣ 입력예제 1

5 14

▣ 출력예제 1

3

▣ 입력예제 2

8 3

▣ 출력예제 2

5

정답 코드

// 정답지 방법
function solution(s, e) {
  // n 번의 위치를 한번 위치한 이후에 다시 위치하지 않기 위한 확인용 배열
  let ch = Array.from({ length: 10001 }, () => 0);
  // n 번의 위치의 레벨을 저장할 배열
  let dis = Array.from({ length: 10001 }, () => 0);
  let queue = [];
  queue.push(s); // 초기 위치 que 에 등록
  ch[s] = 1; // s 위치 방문여부 업데이트
  dis[s] = 0; // s 위치 레벨 0 으로 초기화

  // que 에 위치가 남아있을 때 까지 반복
  while (queue.length) {
    let x = queue.shift(); // 현재 큐에서 맨 앞의 값을 꺼내 x 에 저장

    // x - 1, x + 1, x + 5  각각의 값을 nx 변수에 담아 반복
    for (let nx of [x - 1, x + 1, x + 5]) {
      // e 위치에 도착한 경우 현재 레벨의 값을 반환하여 함수 종료 (dis[x] 는 이전 위치의 레벨 값이므로 + 1 한값이 현재 레벨값을 의미)
      if (nx === e) return dis[x] + 1;

      // 위치가 1보다 크고 최대 위치보다 작고 방문한 경험이 없는 위치인 경우
      // 확인용 배열 업데이트, 큐에 배열에 현재 위치 추가, 현재 위치 레벨값 업데이트 등을 처리
      if (nx > 0 && nx <= 10000 && ch[nx] === 0) {
        ch[nx] = 1;
        queue.push(nx);
        dis[nx] = dis[x] + 1;
      }
    }
  }
}
console.log(solution(8, 3));

풀이

1. n 번의 위치를 한번 위치한 이후에 다시 위치하지 않기 위한 확인용 배열 ch, n 번의 위치의 레벨을 저장할 배열 dis 선언
2. 큐로 활용한 배열 queue 선언후 초기 위치인 s 를 배열에 등록, s 위치 방문여부와 위치 레벨을 초기화 하기 위해 ch 와 dis 에 초기값 등록
3. queue 에 위치가 남아있을 때 까지 반복하며 현재 queue 에 맨 앞의 값을 꺼내 변수 x 에 저장 그 이후 x - 1, x + 1, x + 5 각각의 값을 각각 nx 변수에 담아 반복
4. nx 값이 위치가 1보다 크고 최대 위치보다 작고 방문한 경험이 없는 위치인 경우 이동할 수 있는 상황 이므로 확인용 배열 업데이트, 큐에 배열에 현재 위치 추가, 현재 위치 레벨값 업데이트 등을 처리
5. 만약 nx 값이 e 위치에 도착한 경우 현재 레벨의 값을 반환하여 함수 종료 (dis[x] 는 이전 위치의 레벨 값이므로 + 1 한값이 현재 레벨값을 의미)

오답 노트

※ 주어진 예제는 통과했으나 분명한 오류가 있는 코드

function solution(s, e) {
  let answer = Number.MAX_SAFE_INTEGER;
  let count = 0; // 콩콩이 이동 횟수를 저장할 변수

  let queue = [s];
  while (queue.length) {
    console.log(queue); // 현재 큐 상황
    let temp = queue.pop(); // 현재 큐에서 마지막 값을 꺼내 temp 에 저장

    // 이미 count 를 넘겨버린 경우 확인할 필요가 없으므로 스킵
    if (count >= answer) continue;

    // temp 값이 송아지 위치에 도착한 경우
    if (temp === e) {
      console.log("도착   count: ", count);

      // 도착까지 걸린 이동 횟수가 현재 최소 이동거리보다 작다면 answer 을 업데이트
      if (count < answer) answer = count;

      // 도착 이전 위치에서 다시 이동하는 경우의 수를 따지기 위해 count 를 1 감소
      // ※ 오류 부분 1칸 뒤로 이동하는 경우만큼 - 해야하지만 
      // 1 만 감소했으므로 뒤로 이동하는 경우가 2회 이상인 경우 count 값에 오류가 생긴다
      count - 1;
    }

    // 도착 위치보다 거리가 부족할 때 1칸, 5칸 앞으로 이동하는 경우를 배열에 추가 후 이동 했으므로 count 증가
    if (temp < e) {
      count++;
      queue.push(temp + 1);
      queue.push(temp + 5);
    }

    // 도착 위치를 넘어갈 때 1칸 뒤로 이동하는 경우를 배열에 추가 후 이동 했으므로 count 증가
    if (temp > e) {
      queue.push(temp - 1);
      count++;
    }
  }

  return answer;
}

초기 풀이 방식

1. queue 가 비워질 때까지 반복하며 queue 에서 마지막 값을 뽑아 e 보다 작다면 +1, +5 위치를 순서대로 push 하고 count 증가
2. 위 과정을 반복하다 e 보다 작아지는 경우 다시 -1 위치 queue 에 push 하고 count 증가
3. 결국에 e 위치에 도착하는 경우 현재까지 최소 이동 거리와 비교해 정답 변수에 저장
4. 이후 마지막으로 count 를 1 감소 시켜 이전 위치에서 다시 이동을 시작(오류 부분)

오류

일단 넓이 우선 탐색보다는 +5 이동을 우선으로하기 때문에 깊이 우선 탐색에 조금 더 가까운 풀이 방식도 문제 출제의 의도에 맞지 않는 접근이기도 하고 실제 코드에서도 밑줄 친 부분에 오류가 존재한다.

일단 변수 count 이동 횟수이면서도 트리로 보았을 때 레벨을 의미한다.

위 코드에서는 만약 e 에 도착하는 과정에서 e 위치를 넘어간 이후 몇 번 다시 1칸 뒤로 이동했다면 도착 이후 다시 e 위치를 넘어가기 이전 레벨에서 부터 다시 이동을 시작하기 위해 1칸 뒤로 이동하는 경우만큼 count 를 감소 해야하지만 공통적으로 1 만 감소했으므로 뒤로 이동하는 경우가 2회 이상인 경우 count 값에 오류가 생긴다.

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64156