BFS란? (BFS기본, 송아지찾기 문제)

너비 우선 탐색(BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

 

최단거리를 탐색 할 때 사용된다.

BFS 기본

function solution () {
    let answer = "";
    let queue = [];
    queue.push(1); // root 노드
    
    while(queue.length) {
        let v =queue.shift() + " ";
        answer += v + " ";
        for(let nv of [v*2, v*2+1]) {
            if (nv > 7) continue;
            queue.push(nv);
        }
    }
    return answer;
}
console.log(solution());

 

송아지찾기 (BSF: 상태트리탐색)

문제)

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

입력 설명)

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

출력설명)

점프의 최소횟수를 구한다. 답은 1이상입니다.

입력예제1

입력: 5 14

출력: 3

입력예제2

입력: 8 3

출력: 5

---

풀이 1- 모든 노드의 distance를 저장하는 방법.

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

풀이 2- level을 이용한 방법

function solution (s, e) {
    let answer = 0;
    let ch = Array.from({length:10001}, ()=>0);
    let level=0;
    let queue =[];
    ch[s] = 1;
    queue.push(s);
    while(queue.length) {
        let len = queue.length;
        for (let i=0; i<len; i++) {
            let x=queue.shift();
            if(x===e) return level;
            for(let nx of [x-1, x+1, x+5]) {
                if(nx>0 && nx<=10000 && ch[nx]===0) {
                    ch[nx] =1;
                    queue.push(nx);
                }
            }
        }
        level++;
    }
}
console.log(solution(5, 14));