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

🙋‍♀️넓이우선탐색(BFS)?

🙋‍♀️ Breadth-First Search : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 레벨별 탐색이라고도 한다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
👉 BFS는 재귀적으로 동작하지 않는다.
👉 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
👉 queue라는 자료구조 사용한다.(선입선출)
👉 상태트리
👉 깊이우선탐색과 같이 파고드는 탐색 ❌ back tracking ❌

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

  function solution() {
    let answer = "";
    let queue = [];
    queue.push(1); //root node 넣어주기
    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()); // 1 2 3 4 5 6 7

6. 송아지 찾기(BFS : 상태트리탐색)

현수는 한번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하기.
현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.

  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(5, 14)); //3

또다른 풀이 방식 (Level을 return하는 방식)

  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)); //3

7. 섬나라 아일랜드(DFS)

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하기.

  function solution(board) {
    let answer = 0;
    let n = board.length;
    let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
    let dy = [0, 1, 1, 1, 0, -1, -1, -1];
    function DFS(x, y) {
      board[x][y] = 0;
      for (let k = 0; k < 8; k++) {
        let nx = x + dx[k];
        let ny = y + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) {
          console.log(nx, ny);
          DFS(nx, ny);
        }
      }
    }
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (board[i][j] === 1) {
          // board[i][j] = 0;
          answer++;
          DFS(i, j);
        }
      }
    }
    return answer;
  }
  let arr = [
    [1, 1, 0, 0, 0, 1, 0],
    [0, 1, 1, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 1, 1],
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 0, 0, 1, 0, 0],
    [1, 0, 1, 0, 1, 0, 0],
  ];

  console.log(solution(arr)); //5

7. 섬나라 아일랜드 (BFS 활용)

위의 문제를 BFS를 활용하여 풀어보기

  function solution(board) {
    let answer = 0;
    let n = board.length;
    let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
    let dy = [0, 1, 1, 1, 0, -1, -1, -1];
    let queue = [];
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (board[i][j] === 1) {
          board[i][j] = 0; // queue에 넣기 전에 체크해줘야됌 중복 막으려면!
          queue.push([i, j]);
          answer++;
          while (queue.length) {
            let [x, y] = queue.shift();
            console.log(x, y);
            for (let k = 0; k < 8; k++) {
              let nx = x + dx[k];
              let ny = y + dy[k];
              if (
                nx >= 0 &&
                nx < n &&
                ny >= 0 &&
                nx < n &&
                board[nx][ny] === 1
              ) {
                board[nx][ny] = 0;
                queue.push([nx, ny]);
              }
            }
          }
          console.log("BFS end");
        }
      }
    }

    return answer;
  }

  let arr = [
    [1, 1, 0, 0, 0, 1, 0],
    [0, 1, 1, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 1, 1],
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 0, 0, 1, 0, 0],
    [1, 0, 1, 0, 1, 0, 0],
  ];

  console.log(solution(arr)); //5
  

⭐️중요 포인트) queue에 board[i][j]값 넣기 전에 반드시 값을 0으로 바꾸어주어야 한다. 그렇지 않으면 queue에서 값을 for문을 돌릴 때 출발 점에 다시 오게 된다. (중복 발생)