[Algorithm] 이진트리 너비우선탐색(BFS)

❐ 이진트리 너비우선탐색

▶︎ 문제

   아래 그림과 같은 이진트리를 너비우선탐색해 보세요.

 

▷ 출력 예제

1 2 3 4 5 6 7

 

▶︎ 문제설명

너비우선탐색(BFS, Breadth First Search)은 시작 정점(vertex, 노드)에서 출발해 인접한 모든 정점들을 우선 방문 하는 방법이다. 시작 정점으로부터 멀리 떨어져 있는 정점은 나중에 순회하게 된다. 이런 점에서 앞서 포스팅했던 깊이우선탐색(DFS)과는 양상을 보인다. 

 

혹자는 DFS와 BFS를 드라마를 보는 방식의 차이로 예를 들기도 한다. DFS는 하나의 드라마를 골라서 그것을 정주행해서 시청하며 하나의 시리즈를 다 볼 때까지 다른 드라마는 보지 않는 방식이라고 한다면, BFS는 여러 드라마를 하나씩 보는 방법이라고 할 수 있다. 

 

이러한 차이는 코드에서도 확연히 드러나는데 DFS는 재귀함수를 통해 구현하는 것이 일반적이며 탈출 조건에 도달할 때까지 깊이를 더해가며 호출을 계속한다. 반면 BFS는 큐 자료구조를 이용하는 것이 정석으로 먼저 들어간 데이터가 먼저 나오는 선입선출의 원칙에 따라 1. 가장 먼저 넣었던 정점를 꺼내서 2. 그것과 연결된 정점을 큐에 넣고 3. 큐가 빌때까지 이것을 반복 하는 방식으로  구현할 수 있다.

이를 코드로 확인해보자.

 

▷ 내 답안

function solution() {
    let answer = "";
    let queue = [];
    queue.push(1);
    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());

 

let queue = [];
queue.push(1);

값을 저장할 큐를 만들고 첫번째 정점의 값을 넣어준다. 

 

while (queue.length) {
    let v = queue.shift();
    answer += v + " ";
    ...
}

큐에 값이 남아있지 않을 때까지 첫번째 요소를 제거하고 answer에 문자열을 추가하는 과정을 반복한다.

 

for (let nv of [v * 2, v * 2 + 1]) {
    if (nv > 7) continue;
    queue.push(nv);
}

큐에서 첫번째 요소를 제거 한 후 해당 요소 인접해 있는 정점들을 큐에 추가한다. 

이진트리는 하나의 부모노드와 두 개의 자녀노드를 가진다. 부모노드 하나를 큐에서 제거하면 그와 인접해 있는 두 개의 자녀노드가 큐에 들어가게 될 것이다. 이진트리에서 왼쪽에 위치한 자녀는 (부모노드)*2의 값을 가지고, 오른쪽에 위치한 자녀는 (부모 노드)*2+1의 값을 가진다.

 

 

이를 구현하기 위해 자녀노드의 값이 들어간 [v*2, v*2+1]의 배열을 만들고 for of 문을 통해 큐에 push 한다. 

 

최종적으로 다음과 같은 결과가 출력된다.