자료구조 BFS, DFS

BFS

• BFS는 너비 우선으로 그래프를 탐색하는 알고리즘
• 시작점 인접한 노드를 먼저 탐색하고, 그 다음 인접한 노드들의 인접한 노드를 탐색하는 방식으로 진행

BFS 특징

• 자료 구조: 큐(Queue)를 사용
• 최단 경로: BFS는 모든 간선의 가중치가 동일한 경우, 출발 노드에서 목적지 노드까지의 최단 경로를 찾을 수 있음
• 시간 복잡도: O(V + E) (V: 노드 수, E: 간선 수)

js로 구현한 BFS

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();

    if (!visited.has(node)) {
      visited.add(node);
      queue.push(...graph[node]);
    }
  }

  return visited;
}

BFS의 동작 원리

1. 탐색을 시작할 노드를 큐(Queue)에 넣고 방문 처리
2. 큐에서 노드를 꺼내 그 노드에 인접한 노드들을 모두 탐색
3. 인접한 노드 중 아직 방문하지 않은 노드를 큐에 추가하고, 이를 반복
4. 큐가 비어있으면 탐색이 종료

DFS

• DFS는 깊이 우선으로 그래프를 탐색하는 알고리즘
• 한 노드를 탐색하면 그 노드와 연결된 노드를 깊게 들어가 탐색하고, 더 이상 탐색할 수 없을 때 다시 되돌아와 다른 경로를 탐색하는 방식으로 진행

DFS 특징

• 자료 구조: 스택(Stack) 또는 재귀 호출 사용
• 경로 탐색: DFS는 경로 탐색에서 모든 경로를 확인할 수 있지만, 반드시 최단 경로를 찾는 것은 아님
• 시간 복잡도: O(V + E) (V: 노드 수, E: 간선 수)

js로 구현한 DFS

function dfs(graph, start, visited = []) {
  visited.push(start);

  graph[start].forEach((node) => {
    if (!visited.includes(node)) {
      dfs(graph, node, visited);
    }
  });

  return visited;
}

DFS 코드 설명

1. 탐색을 시작할 노드를 스택(Stack) 또는 재귀 호출로 탐색
2. 현재 노드를 방문 처리하고, 인접한 노드 중 아직 방문하지 않은 노드를 선택하여 탐색을 계속 진행
3. 더 이상 방문할 노드가 없으면, 이전 노드로 돌아가서 다른 경로를 탐색
4. 모든 노드를 방문하면 탐색이 종료

BFS와 DFS의 차이점

특징	BFS	DFS
탐색 방식	너비 우선 탐색 (인접한 노드를 먼저 탐색)	깊이 우선 탐색 (하나의 경로를 끝까지 탐색)
자료 구조	큐(Queue)	스택(Stack) 또는 재귀 호출
경로 탐색	최단 경로 보장	모든 경로 탐색, 최단 경로는 보장하지 않음
적용 상황	최단 경로 찾기, 레벨 탐색	경로의 존재 여부 탐색, 모든 경로 확인
시간 복잡도	O(V + E)	O(V + E)

BFS와 DFS의 활용 예시

• BFS 활용 예시:
  • 최단 경로 탐색: 예를 들어, 지하철 노선도에서 출발점에서 목적지까지의 최소 환승 횟수를 구하는 문제에서 BFS는 매우 유용하게 사용 됨
• DFS 활용 예시:
  • 미로 탐색: 모든 경로를 탐색해야 하는 문제에서 DFS가 유용하게 사용 됨. (한 경로를 끝까지 탐색한 뒤, 다른 경로로 전환하는 방식)