개념

• DFS
  • 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
  • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
• BFS
  • 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
  • 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

이동경로 순서 비교

구현 방식

• DFS: Stack 혹은 재귀함수(Recursion)

• BFS: Queue

시간 복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다.

DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.

• 인접 리스트 : O(V + E), 즉 O(n)
• 인접 행렬 : O(V^2)

코드

const DFS = function (node) {
  let answer = "";
  const visited = new Array(N + 1).fill(false, 0, N + 1);
  const stack = [];

  stack.push(node);

  while (stack.length > 0) {
    const cur = stack.pop();

    if (!visited[cur]) {
      visited[cur] = true;
      answer += cur + " ";

      for (let next = N; next >= 1; next--) {
        if (!visited[next] && graph[cur][next]) {
          stack.push(next);
        }
      }
    }
  }

  return answer;
};

const BFS = function (node) {
  let answer = "";
  const visited = new Array(N + 1).fill(false, 0, N + 1);
  visited[node] = true;

  const Queue = [];
  Queue.push(node);

  while (Queue.length > 0) {
    const cur = Number(Queue.shift());
    answer += cur + " ";

    for (let next = 1; next <= N; next++) {
      if (!visited[next] && graph[cur][next]) {
        visited[next] = true;
        Queue.push(next);
      }
    }
  }

  return answer;
};