송아지 찾기

BFS원리

• 첫번째 들어가는 숫자= x
• 그 밑은 nx of [x-1, x+1, x+5]
  즉, x로 구할수 있는 모든 경우의 수는 아랫층에 위치
• dis는 distance의 약자로 5로부터 얼마나 떨어져 있나를 측정
  예를들어 5바로 밑의 4는 한칸 떨어져 있으므로 dis[4]=1로 표시하여 거리 측정.
• dis[x]=2에서 5, 11같은 나왔던 숫자가 또 나올경우 ch[5]=1,ch[11]=1과 같이 표시하여 나왔던 숫자를 골라낸다.
• 목표하는 숫자가 나오면 거리를 출력

자세한 BFS원리: https://velog.io/@polynomeer/너비-우선-탐색BFS

코드

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

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