송아지 찾기!(BFS)

문제설명

철수가 강아지를 잃어버렸다.

현수는 스카이콩콩(...)을 타고 송아지를 찾으러 갈건데

점프 한번에 뒤로한칸 또는 앞으로 한칸 또는 앞으로 5칸을 갈 수 있다.

현수의 위치를 h칸

송아지의 위치를 c칸 라고 했을 때

h칸에서 c칸으로 가기 위한 최소 점프 횟수를 구하는 함수를 완성해라.

단, h 와 c는 1과 10000사이의 정수 이다.

 

ex)h=5 c=14

     result=3

접근방법

ㅎ 문제 한번 괴랄하네

스카이콩콩이라니 ㅎㅎ

일단 트리를 만들어서 어떻게 코드를 짤지 생각을 해봤다.

 

ㅎ...그림이 중요한게 아니니까...ㅎ

대충 이런 식으로 생긴 트리다

루트노드 h 인 5로 시작하고

-1, +1, +5 세가지 경우로 자식노드 생기고

14를 찾을 때 까지 반복 한다는 거다.

최단 거리를 찾는 문제니까

BFS를 이용하면 된다.

왠지 모르게 풀 수 있을것 같은 자신감이 들었다.

 

function getJump(h, c) {
  const moving = [-1, 1, 5];
  let count = 0;
  let queue = [];
  queue.push(h);
  while (true) {
    const checkNum = queue.shift();
    if (checkNum === c) return count;

    for (const move of moving) {
      queue.push(checkNum + move);
      count++;
    }
  }
}
console.log(getJump(5, 14));  // 63

 

패기롭게 짠 코드다.

움직일수 있는 칸수를 배열로 정리하고

queue에다가 넣었다 뺐다 하면서

카운트에 숫자를 늘려준다.

3이 출력되야 되는데

63이 출력 돼서 멘탈이 갈렸다.

부서진 멘탈을 주섬주섬 주워담고

찬찬히 코드를 살펴 봤다.

위의 그림의 레벨을 출력 해줘야 되는데

간선을 이동할때 마다 카운터에 1을 추가하고 14를 찾으면 카운터를 리턴한다.

잘못짠 코드다.

한 20분을 이것저것을 해보다가,

우리집 시니어랑 같이 생각해봤다.

우리집 시니어는 확실히 다르다 금새 답을 찾았다.

 

function solution(h, c) {
  const moving = [-1, 1, 5];
  let queue = [];
  queue.push([h, 0]);
  while (true) {
    const [checkNum, level] = queue.shift();
    if (checkNum === c) return level;

    for (const move of moving) {
      queue.push([checkNum + move, level + 1]);
    }
  }
}

 

첫 push해주는 값이 h 와 0 으로 만든 배열이다.

여기서 0은 level을 나타낸다

그리고 while문에서 shift 배열을 queue에서 빼내면서

checkNum 과 level을 정의한다.

if 문에서 얼리 리턴을 위해 

리턴 조건을 명시해놨다. 

checkNum이랑 c가 일치하면 level을 리턴한다.

일치하지 않는다면, 

체크 넘에다가 moving배열에 있는 value들을 더해주고

level에도 1을 더해준 뒤

queue에 넣어준다.

checkNum과 c가 일치할때 까지 반복.

경이롭다.

이게 짬에서 나온 바이브인가 보다.

 

 

이게 인프런 강의에서 나온 문제인데 강의에서 풀이까지 해준다.

인프런 센세가 짠 코드를 보면.

function solution2(h, c) {
  const location = Array.from({ length: 10001 });
  const queue = [];
  location[h] = 0;
  queue.push(h);

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

    for (const nx of [x - 1, x + 1, x + 5]) {
      if (nx === c) return location[x] + 1;

      if (nx > 0 && nx <= 10000 && location[nx] === undefined) {
        queue.push(nx);
        location[nx] = location[x] + 1;
      }
    }
  }
}

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

 

이게.. 글로만 설명하긴 좀 복잡한데..

우선 저 location에 할당 된 배열이 키포인트다.

 

0	1	2	3	4	5	6	7	.......	10000
undefined	undefined	undefined	undefined	undefined	undefined	undefined	undefined	.......	undefined

윗줄은 index고 아랫줄이 value다.

그리고 location[h] 즉, 예시를 입력하면 location[5]에 0을 할당한다.

0은 level 이다.

0	1	2	3	4	5	6	7	.......	10000
undefined	undefined	undefined	undefined	undefined	0	undefined	undefined	.......	undefined

요렇게 변한거다.

그리고 queue에다가 5를 넣어준다.

 

while 조건문에 들어있는건 딱히 큰 역할이 없다. 

length 가 0 이 되기 전에 리턴을 해줄거기 때문에

그냥 true적어도 상관 없더라.

queue에서 shift로 빼낸 값을 x에 할당해주고

for of 의 조건문안에 x에서 -1, +1, +5를 해준 값들을 nx으로 지정하고

반복문을 돌린다.

nx에 할당 된 값이 c와 일치하면

location[x]의 값에 1을 더해준 값을 리턴한다.

 

nx가 c와 일치하지 않고,

1과 10000사이에 있는 수이며, 

location[nx]가 undefined 이면

location[nx]에 location[x]의 값에 1을 더해준 값을 할당해준다.

 

그니까.. 1회차가 끝난 후 location의 배열은

0	1	2	3	4	5	6	7	.......	10000
undefind	undefind	undefind	undefind	1	0	1	undefind	.......	undefind

location[4],[6], [10] 의 값에 1이 할당 되어있다.

3회차에 nx는 14가 될거고

location[x]의 값은 2일 것이다.

그러니 리턴되는 값은 location[x]에 1이 더해진 값 3이다.

 

쥰내 아름답다.

코드 설명을 들으면 이해는 되는데

내가 저 설명을 듣기 전에 짠다고 생각하면

막막하기만 하다.

그래도 오늘은 어떻게 접근 할지도 몰랐던 어제와는 달리

이렇게 하면 되지 않나..?

정도는 했으니까 장족의 발전이 아닐까 싶다.