DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)

SungWoo·2024년 12월 29일

목록 보기

8/8

그래프 탐색 알고리즘은 그래프라는 자료구조에서 특정 노드들을 방문하거나, 노드 간의 관계를 파악하기 위해 사용되는 알고리즘이다. 그래프는 정점(노드)과 간선(엣지)으로 이루어진 자료구조로 각 정점 간의 연결 상태를 나타낸다. 탐색 알고리즘은 이러한 그래프 구조를 기반으로 다음과 같은 작업을 수행할 수 있다.

특정 노드 탐색: 특정 노드가 그래프에 존재하는지 확인한다.
경로 탐색: 두 노드 사이의 경로가 존재하는지, 혹은 그 경로가 어떤 것인지 찾는다.
최단 거리 계산: 두 노드 간의 최단 경로를 계산한다.
연결성 확인: 그래프가 연결되어 있는지, 즉 모든 노드가 서로 연결되어 있는지 확인한다.

그리고 그래프를 탐색하는 방법은 크게 두가지로 나뉜다.

DFS(깊이 우선 탐색)
BFS(너비 우선 탐색)

이 두 탐색 방법은 문제의 성격에 따라 적합성이 달라지므로 지금부터 이 두 탐색 방법에 대해 정리해보자.

DFS(Depth-First Search)

DFS는 그래프를 탐새할 때 한 경로를 끝까지 탐색한 후에 다른 경로를 탐색하는 방식이다.

마치 미로를 탐험할 때 한 길을 끝까지 가보는 것과 비슷한데, 한 방향으로 갈 수 있는 만큼 깊이 들어가다가, 더 이상 갈 수 없으면 다시 돌아와서(백트래킹) 다른 경로를 탐색한다.

구현 방법: 재귀 또는 호출 스택 사용
특징
- 특정 경로를 완전히 탐색해야 하는 경우에 유용하다.
- 메모리 사용량이 적으나, 경로가 깊으면 스택 오버플로우가 발생할 수 있다.
- 최단 경로를 보장하지 않는다.
사용 사례: 퍼즐 문제(미로 찾기), 순열/조합 생성, 백트래킹 문제

DFS 코드 예시

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'E'],
  D: ['B'],
  E: ['C']
};

function dfs(graph, start) {
  const visited = new Set();
  
  function explore(vertex) {
    // 방문 표시
    visited.add(vertex);
    console.log(vertex); // 방문한 노드 출력
    
    // 인접한 노드들을 탐색
    for (let neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        explore(neighbor);
      }
    }
  }
  
  explore(start);
}

// 사용 예시
dfs(graph, 'A'); // 출력: A, B, D, C, E

BFS(Breadth-First Search)

BFS는 그래프를 탐색할 때, 현재 노드의 인접한 노드를 탐색한 후, 그 다음 단계로 넘어가는 방식이다.

이것은 마치 물결이 퍼져나가는 것처럼, 시작점에서 가까운 것부터 차례대로 탐색하는 방법이다. 현재 위치에서 도달할 수 있는 모든 곳을 먼저 방문한 후, 그 다음 레벨로 넘어간다.

구현 방법: 큐 사용
특징
- 최단 경로를 보장(가중치가 동일한 경우)
- 메모리 사용량이 많다.(모든 노드를 큐에 저장하기 때문)
사용 사례: 최단 경로 탐색, 레벨별 탐색(ex. 네트워크 연결, 소셜 그래프)

BFS 코드 예시

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  
  while (queue.length > 0) {
    const vertex = queue.shift(); // 큐에서 첫 번째 요소를 꺼냄
    
    if (!visited.has(vertex)) {
      visited.add(vertex);
      console.log(vertex); // 방문한 노드 출력
      
      // 인접한 노드들을 큐에 추가
      for (let neighbor of graph[vertex]) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
}

// 사용 예시
bfs(graph, 'A'); // 출력: A, B, C, D, E