Algorithm JS - 송아지 찾기

jiny·2023년 3월 11일
0

JavaScript Algorithm

목록 보기
19/23
post-thumbnail

문제

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

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

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

입력예제 1
5 14

출력예제 1
3

입력예제 2
8 3

출력예제 2
5

풀이

  1. 체크 배열(중복된 값을 queue에 넣지 않기 위함)과 dis 배열을 설정(1 ~ 10000)
  2. 현수의 위치를 체크 배열에 체크 후 queue에 추가
  3. 현수의 출발 지점을 dis 배열에 0으로 설정
  4. while 순회하며 출발 지점에서 +1, -1, +5만큼 각각 이동
  5. 만약 이동한 값이 목표 지점에 도달하면 queue에서 꺼낸 값의 레벨에 +1 한 값을 리턴
  6. 도달하지 못했다면 체크 배열에 +1 -> 큐에 nx 추가 -> 부모 노드 level에서 +1한 값을 자식노드에 더함

코드

1) dis 배열로 푸는 경우

function solution(s, e) {
  let answer = 0;
  // 체크 배열과 distance를 위한 배열
  let ch = Array.from({ length: 10001 }, () => 0);
  let dis = Array.from({ length: 10001 }, () => 0);
  let queue = [];
  // 출발 지점 1로 체크
  ch[s] = 1;
  queue.push(s); // 출발 지점 push
  dis[s] = 0; // 현수의 출발 지점을 0레벨로 설정
  while (queue.length) {
    let x = queue.shift();
    // +1, -1, +5칸 이동 (nx는 기존 x에서 +1, -1, +5 이동한 값)
    for (let nx of [x - 1, x + 1, x + 5]) {
      // 목표지점에 도달할 경우 다음 값을 리턴
      if (nx === e) return dis[x] + 1;
      // 목표 지점에 도달하지 못할 경우
      if (nx > 0 && nx <= 10000 && ch[nx] === 0) {
        // 체크 배열 +1 -> 큐에 nx 추가 -> 부모 노드 level에서 + 1 한 값을 자식 노드에 추가
        ch[nx] = 1;
        queue.push(nx);
        dis[nx] = dis[x] + 1;
      }
    }
  }
  return answer;
}

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

2) level로 푸는 경우

function solution(s, e) {
  let answer,
    L = 0;
  let ch = Array.from({ length: 10001 }, () => 0);
  let queue = [];
  queue.push(s);
  ch[s] = 1;
  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));

0개의 댓글