// JavaScript 구현
const graph = {
  1: [2, 3],
  2: [4, 5],
  3: [6, 7],
  4: [],
  5: [],
  6: [],
  7: []
};

function bfs(graph, startNode) {
  const visited = new Set([startNode]);
  const queue = [startNode];
  const result = [];
  
  // shift()의 O(N) 방지를 위한 투 포인터 방식 권장
  let head = 0; 
  
  while (head < queue.length) {
    const node = queue[head++]; // O(1) 추출
    result.push(node);
    
    // 인접 노드들을 레벨 단위로 모두 큐에 삽입
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}

console.log("BFS 탐색 결과:", bfs(graph, 1).join(" -> "));
// 출력 결과: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7