2022/05/09) 6. 송아지 찾기(BFS : 상대트리탐색) [그래프와 탐색(DFS, BFS(넓이우선))]

1. 문제

<송아지 찾기>
: 현수는 송아지를 잃어버렸다. 현수의 위치와 송아지의 위치가 수직선상의 좌표점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프는 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성한다. 점프의 최소횟수를 구하라.
(첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000이다.)

2. 해결 방법

1. 나는 (송아지거리 - 현수거리)해서 구하려 했는데, BFS는 5라는 출발지점에서 시작하여(level 0), -1 / +1 / +5 총 3가지 경우로 뻗어간다(level 1).
2. 주의해야 할 점은, 이미 queue에 들어갔던 좌표의 값들을 또 넣지 않도록 한다. level 0에서 5나, level 2에서 5(5(시작지점)-1+1)나 결국 똑같고 시간만 더 복잡해지기 때문이다. 그리하여 ch배열을 생성하여 확인 후 push해준다.
3. 몇 번만에 갔는지 답을 구하려면, level로 구하여도 되지만 dis배열을 생성하여 dis[nv]=dis[v]+1;하여 값을 구하여도 된다.
   (그림에선 v(vertex), nv(next vertex)라고 표현했지만, 코드에선 x(좌표)/nx로 표현함)

3. 정답

        <script> //distance 배열로 답 구하기
            function solution(s, e){ 
                let answer = 0;
                let ch = Array.from({length:10001},()=>0); //좌표 점이 1부터 10,000까지므로 dis배열은 10,001까지 있어야 함. (인덱스 0때문에)
                let dis = Array.from({length:10001},()=>0);
                let queue = [];
                ch[s]=1; //출발지점 체크
                queue.push(s); //출발지점 삽입
                dis[s]=0;
                while(queue.length){
                    let x = queue.shift(); //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){
                            ch[nx]=1;
                            queue.push(nx);
                            dis[nx]=dis[x]+1;
                        }
                    }
                }
                return answer;
            }
            console.log(solution(8,3));
        </script>

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

4. 내 코드와 비교 그리고 반성

BFS로는 못짜고 그냥 규칙 파악해서 코드를 짰다. 근데 자바스크립트 Math함수를 다 까먹어서 console.log해서 그냥 하나하나 해봤다. 그러다가 round라는 것을 발견했다. 나머지가 1,2이면 내리고, 3,4이면 올리고! 사실 이전에 공부했던 거 같은데 기억이.. 아마 소수점 반올림할때 한 듯하다. 아무튼 이거랑 음수를 양수로 만들어주는 abs를 이용해서 했다. /는 몫을 반환, %는 나머지를 반환. 진짜 정신좀 차리자.. 이런 거까지 까먹다니.. 요즘 드는 생각인데 멍청한 거도 죄인 거 같다. 아무튼 round덕분에 나머지가 3,4일 때 1을 더하지 않아도 되었다. 가독성도 떨어져서 빡친다.

        <script>
            function solution(s, e){  //S가 현재 위치, e가 송아지 위치. 앞으로 1, 뒤로 1, 앞으로 5 이동 가능
                let answer = 0;
                //Math.round : 나머지가 1,2면 내림, 3,4면 올림
                let tmp = e - s; //9
                if(tmp > 0){
                    let rest = (tmp%5); 
                    if(rest === 0){
                        answer = tmp/5;
                    } else if(rest === 1 || rest === 2){
                        answer = Math.round(tmp/5) + rest; //11 나누기 5 : 몫 2, 나머지 1
                    } else{ //나머지가 3이나 4일 때
                        answer = Math.round(tmp/5) + (5-rest); 
                    }
                }
                if(tmp < 0) answer = Math.abs(tmp);
                return answer;
            }
            console.log(solution(5, 20));
        </script>