코딩 테스트 공부 : BFS/DFS

오늘은 BFS/DFS에 대해 공부해보았다.

BFS/DFS?

<이미지 출처> : https://en.wikipedia.org/wiki/Breadth-first_search

BFS는 너비 우선 탐색으로 트리 구조의 데이터에서 노드의 인접 데이터를 모두 탐색한 뒤, 다음 데이터로 이동하는 방법이다. 보통 최단 거리를 구하는 것에 사용된다고 한다.

// BFS 구현 코드

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
}

const bfs = (graph, startNode) => {
  let visited = []; // 탐색을 마친 노드
  let needVisit = []; // 탐색 해야 할 노드

  needVisit.push(startNode) // 노드 탐색 시작
  
  // 탐색 해야 할 노드가 남아있다면, queue이기 때문에 선입선출로 shift()를 사용. 
  while(needVisit.length !== 0){
    const node = needVisit.shift()
    if(!visited.includes(node)){
      // 해당 노드가 탐색된 적이 없다면
      visited.push(node)
      needVisit = [...needVisit, ...graph[node]]
    }
  }
  return visited
}

console.log(bfs(graph, "A"))
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

<이미지 출처> : https://en.wikipedia.org/wiki/Depth-first_search

DFS는 깊이 우선 탐색으로, 트리 구조의 데이터에서 노드마다 가장 깊이까지 탐색한 뒤 다음 노드로 이동하는 방법이다. 보통 경로 구하는 것에 사용된다고 한다.

// DFS 구현 코드

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const dfs = (graph, startNode) => {
  const visited = [] // 탐색 마친 노드
  let needVisit = [] // 탐색 해야 할 노드

  needVisit.push(startNode) // 노드 탐색 시작

  // 탐색 해야 할 노드가 남아 있다면, queue이기 때문에 shift() 사용(선입선출)
  while(needVisit.length !== 0){
    // 해당 노드가 탐색된 적이 없다면
    const node = needVisit.shift()
    if(!visited.includes(node)){
      visited.push(node)
      needVisit = [...graph[node], ...needVisit]
    }
  }
  return visited
}

console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]