1. 염소를 찾자

현재 나의 위치가 주어지고 염소의 위치가 주어졌다. 그리고 내가 한번에 갈 수 있는 거리가 주어진다. 이때 최소한의 움직임으로 염소까지 간다고 했을때 움직였던 횟수를 구하면 된다.

구체적 예를 들어 말해보자.
나의 위치: 5
염소위치: 14
한 번에 움직일 수 있는 거리: -1, 1, 5

이때 5에서 14까지 가는 최소과정은 이렇다 5 ->(-1) 4 ->(5) 9 ->(5) 14 따라서 3번만에 가므로 답은 3이다.

2. 접근 방법

queue를 이용해야한다. 5에서 갈 수 있는 경우를 children 으로 보고 계속 밑으로 뻗어가는 것이다. children을 queue에 더하고 그 앞에서 shift한다음 또 다시 children을 구하면 된다.

• Pseudo code
  • result 와 queue 배열을 만든다
  • 그리고 queue에 현재 위치를 push한다. 일종의 root를 생성하는 작업이다.
  • queue에서 뽑아서 갈 수 있는 거리에 따라 children을 만들어낸다
  • result에 children이 있으면 건너뛰고 없으면 children위치에 배열을 만든다.
    • 그 배열안에 부모배열을 할당하고 거기에 자신을 push하여 경로를 갱신한다.
  • 염소 위치가 되었을때 break한다.

그림으로 나타내면 아래와 같다

           5
        /  |  \
       4   6  10
    /  |  \
   3   5   9
... ... /  |  \
       8   10  14(끝!)

function findGoat(h, g) {
  let result = [];
  let queue = [];

  queue.push(h);
  result[h] = [h];

  while (queue.length) {
    let node = queue.shift();
    if (node === g) {
      break;
    }
    // result 에 푸시하고 싶은데 아래 child중에 뭐가 답으로 가는 길인지 모른다.
    // 확인할 수 있는 방법이 있을까?
    // node === g에서 손을 보면 뭔가 실마리를 찾을 수 있을것 같기도 하다.
    for (let child of [node - 1, node + 1, node + 5]) {
      // console.log(node, child);
      if (result[child]) continue;
      else {
        queue.push(child);

        result[child] = result[node].slice();
        result[child].push(child);
      }
    }
  }

  return distance[g];
}
findGoat(5, 14);
// [5,4,9,14]

경로를 구현하는데 조금 오래 걸렸다. 사실은 간단한건데 너무 어렵게 생각한것 같다.

어려웠던 점

result[child] = result[node].push(child) 라고 하면 노드에 push가 되면서 동시에 우항에 node의 length가 리턴이 되면서(push를 하면 array의 길이가 리턴됨) child에 length가 저장됨.

따라서 위의 코드처럼 따로 따로 해줘야 한다. slice를 사용해서 얕은 복사하는 것도 잊지말자.

와.... 진짜 1시간정도 고민해서 구현했다... 별거아니지만 고민끝에 발견해낸 기쁨이 너무 크다
진짜 이맛에 한다. 너무 감격스럽고 눈물날 것 같다 진짜로.

어렵게 생각하지 말고 차분히 정답에 도달하기 위한 과정을 시각화 시키고 시도해보면 된다.