BFS 넓이우선탐색 - JavaScript

BFS는 넓이 우선 탐색이다. 넓이를 우선적으로 탐색하는 것인데, 위의 경우 탐색순서가 다음과 같다.

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

숫자를 순서대로 따라가보면 옆으로 나열하듯 탐색하는 것을 알 수 있다.

const store = {
      root: {
        id: 1,
        type: 'dir',
        name: 'first dir',
        sub: [
          {
            id: 2,
            type: 'dir',
            name: 'first dir',
            sub: [
              {
                id: 9,
                type: 'dir',
                name: 'first dir',
                sub: [],
              }
            ],
          },
          {
            id: 8,
            type: 'dir',
            name: 'first dir',
            sub: [
              {
                id: 4,
                type: 'dir',
                name: 'first dir',
                sub: [],
              }
            ],
          }
        ],
      },
    };

위와 같은 폴더 구조가 있다고 가정해 보자.

넓이 우선탐색으로 탐색하려면 탐색 id 순서는 다음과 같다. 1 -> 2 ->  8 ->  9 -> 4

 

const findDepth = (root, id) => {
  const queue = [root, 'level'];
  let levelCount = 0;

  while (queue.length !== 1) {
    const firstNode = queue.shift();

    if (firstNode.id === id) {
      break;
    }

    if (firstNode === 'level') {
      levelCount += 1;
      queue.push('level');
    }

    if (firstNode !== 'level') {
      queue.push(...firstNode.sub);
    }

    if (queue.length === 1 && firstNode.id !== id) {
      return -1;
    }
  }

  return levelCount;
};

위 코드를 짜면서 깊이를 어떻게 지정해 주는 지 생각해내는 것이 관건이었다.

깊이는 flag를 주어 풀면된다.

1, flag, 2, 8, flag, 9, 4 

flag를 넣어주어 flag를 만날때마다 levelCount를 하나씩 올려주면 된다.

 

참고: https://jun-choi-4928.medium.com/javascript%EB%A1%9C-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B9%8A%EC%9D%B4%EC%99%80-%EB%84%88%EB%B9%84-%EA%B5%AC%ED%95%98%EA%B8%B0-884f6eae5e21