[JS] 코딩 테스트 문제 : 이진트리 넓이 우선 탐색 [BFS]

문제 : 이진트리 넓이 우선 탐색(BFS)

문제 설명

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

넓이 우선 탐색 : 1 2 3 4 5 6 7

넓이 우선 탐색 (BFS) 설명

트리나 그래프를 순회할 때 레벨 순서대로 탐색하는 알고리즘입니다. BFS를 구현할 때는 큐(queue)를 사용하여 각 노드를 탐색 순서대로 저장하고 처리합니다.

상태 트리 탐색, 최단 거리 계산 등에 활용 할 수 있다.

내코드

function solution() {
  let answer = ""; // 탐색한 노드들의 순서를 문자열로 저장할 정답 변수

  // 너비 우선 탐색을 처리할 재귀함수
  // num : 현재 레벨의 가장 낮은 수를 의미하는 인자
  // lever : 현재 트리에서 탐색할 노드의 레벨을 의미하는 인자
  function BFS(num, level) {
    // 현재 레벨에 존재하는 제일 큰 마지막 수(레벨^2 - 1 ) 를 변수 last 에 저장
    let last = 2 ** level - 1;

    // 현재 레벨의 가장 낮은 수의 노드부터 가장 높은 수의 노드까지 반복
    for (let i = num; i <= last; i++) {
      if (i > 7) return; // 7 을 넘어가는 노드의 경우 노드를 탐색하지 않고 함수 종료
      answer += i + " "; // 탐색한 노드를 정답 변수에 문자열 추가
    }
    console.log(level, answer);

    // 현재 레벨의 마지막 노드에 + 1 값이 다음 레벨의 가장 낮은 노드 숫자와 다음 레벨을 매개변수로 BFS 함수를 재귀적으로 호출
    BFS(last + 1, level + 1);
  }

  BFS(1, 1); // 1 노드, 1 레벨 부터 시작
  return answer;
}

console.log(solution());

풀이

1. 현재 레벨의 가장 낮은 수를 의미하는 인자 num 과 현재 트리에서 탐색할 노드의 레벨을 의미하는 인자 level 를 가지는 재귀함수 BFS 를 선언
2. 함수 내에서 현재 레벨에 존재하는 제일 큰 마지막 수(레벨^2 - 1 ) 를 변수 last 에 저장
3. 이후 함수 내에서 num 부터 last 까지 반복하며 노드들을 각각 anwer 문자열에 추가 만약 7 을 넘어가는 노드의 경우 모두 탐색 했으므로 더 이상 탐색하지 않고 함수 종료

오답 노트

위 코드는 너비 우선 탐색(BFS)에 대한 지식이 부족한 상태에서 재귀함수를 이용하여 구현한 코드이다.

현재 노드의 레벨과 시작 노드들을 기준으로 재귀적으로 함수를 호출해가며 레벨 단위에서 노드들을 탐색하고 정답 문자열에 추가하는 방식으로 구현했다.

하지만 재귀함수 특징상 각 호출마다 스택에 호출정보를 저장하므로 만약 많은 노드들을 처리한다면 성능에 문제가 생길 수 있으므로 반복문 및 큐를 활용해 구현하는 방식이 성능이나 가독성 등등 더 효율적일 수 있다.

아래는 반복문과 큐를 활용해 구현한 예시 코드이다.

// 정답지 방법
function solution() {
  let answer = "";
  let queue = [];
  queue.push(1); // 첫번째 노드 삽입

  // 큐가 모두 비워질 때까지 반복
  while (queue.length) {
    console.log(queue);

    // 현재 큐에 맨 앞있는 노드를 탐색한 것으로 보고 큐에서 제외
    let v = queue.shift(); 
    answer += v + " ";

    // 탐색 완료된 노드에 하위 노드가 있다면 존재할 2 개의 숫자들(v * 2, v * 2 + 1)을 순서대로 반복 
    // 하위 노드가 있는 존재하는 노드의 겨웅 하위 노드를 큐에 추가  ex) 2 노드를 탐색한 경우 4,5 노드 추가
    for (let nv of [v * 2, v * 2 + 1]) {
      // 7이 넘어가는 수는 하위 노드가 존재할 수 없으므로 하위노드 생성과정을 생략
      if (nv > 7) continue;

      queue.push(nv); // 하위 노드를 큐에 추가 
    }
  }
  return answer;
}

console.log(solution());

풀이

1. 큐로 사용할 배열 queue 선언 후 기본 값으로 노드 1 삽입
2. 큐가 모두 비워질 때까지 반복문 안에서 현재 큐에 맨 앞있는 노드를 탐색한 것으로 간주하고 큐에서 꺼내 answer 문자열에 추가
3. 탐색 완료된 노드에 하위 노드가 있다면 하위 노드 숫자들(v * 2, v * 2 + 1)을 순서대로 반복하며 하위 노드를 큐에 추가 만약 하위 노드가 없다면 생략

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64155