[CS] DFS, BFS

Kled·2023년 7월 17일

[CS]

목록 보기

5/7

Algorithm

그래프 탐색

깊이 우선 탐색 (Depth First Search: DFS)

그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 나아간다라는 방법을 우선으로 탐색한다.

-> 한 갈래로 갈 수 있는 만큼 최대한 깊게 파고들면서 탐색한다.

연결할 수 있는 정점이 있을 때까지 계속 연결하다가 더 이상 연결될 수 있는 정점이 없으면 바로 그 전 단계의 정점으로 돌아가서 연결할 수 있는 정점이 있는지 살펴봐야 할 것이다.

-> 미로를 탐색할 때 막 다른길에 마주하면 지나온 길을 되돌아간다.

어떤 자료구조를 사용해야할까? 바로 Stack 이다.

-> 스택은 가장 최근에 추가된 요소가 가장 먼저 제거되는 특징을 가지고 있다. 이를 활용하여 현재 위치에서 이동 가능한 정점을 스택에 추가하고, 계속해서 스택에서 가장 최근에 추가된 정점을 꺼내어 이동하는 것이 DFS 알고리즘의 핵심 아이디어이다.

DFS의 특징

모든 노드를 탐색해야 할때 활용하기 좋은 방식이다.
백트래킹을 사용해야 할 때 유용하다. (조합(combination) 사용 시)
깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

DFS 알고리즘

루트노드에서 시작한다.
루트노드와 인접하고 방문된 적 없는 노드를 방문한다. (가장 깊은 노드까지)
인접하고 방문된 적 없는 노드가 없을 경우 (가장 깊은 노드를 방문한 뒤) 갈림길로 돌아와 다른 방향의 노드를 방문한다.

            [A]
           /   \
        [B]     [C]
        / \      |
      [D] [E]    |
            \    |
             \   |
              \  |
               \ |
                \|
                [F]


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


// 방문한 노드를 저장할 배열 선언
const visited = []

function dfs(node) {
  visited.push(node);  // 현재 노드를 방문한 것으로 표시

  const neighbors = graph[node]; // 인접노드들
  for (let i = 0; i < neighbors.length; i++) {
    const neighbor = neighbors[i]; // 인접 노드
    if (!visited.includes(neighbor)) { // 방문하지 않았다면
      dfs(neighbor);  // 방문하지 않은 인접한 노드에 대해 재귀적으로 DFS를 호출.
    }
  }
  return visited
}

// 루트 노드 'A'부터 시작
dfs('A');

너비 우선 탐색 (Breadth First Search: BFS)

BFS는 한 정점에서 시작하여 연결된 정점들을 레벨 순서로 탐색하는 방법이다.
시작 정점을 큐에 넣고, 큐에서 정점을 꺼내면서 연결된 정점들을 큐에 추가하는 방식으로 진행

-> 깊게(deep) 탐색하기 전에 넓게(wide) 탐색
-> 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용하는 방법

BFS 예시

0 노드(시작 노드)를 방문. (방문한 노드 체크)
큐에 방문한 노드를 삽입. enqueue
초기 상태의 큐에는 시작 노드만 저장되어 있다.
즉, a노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다 !
큐에서 꺼낸 노드와 인접한 노드들을 모두 차례대로 방문.
큐에서 꺼낸 노드를 방문
큐에서 꺼낸 노드와 인접한 노드들을 방문
인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다. dequeue
큐에 방문된 노드를 삽입. enqueue
10.큐가 다 소진될 때까지 계속 반복.

BFS 장점

노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
단순 검색 속도가 DFS보다 빠르다.
최단 경로가 존재한다면 어느 한 경로가 무한히 깊어진다고 해도 최단 경로를 반드시 찾을 수 있다.

// 그래프의 인접 리스트를 사용하여 그래프를 표현합니다.
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

function bfs(startNode) {
  const visited = [];  // 방문한 노드를 저장할 Set 객체를 생성합니다.
  const queue = [];  // 큐를 초기화합니다.
  queue.push(startNode);  // 시작 노드를 큐에 넣습니다.
  visited.push(startNode);  // 시작 노드를 방문한 것으로 표시합니다.

  while (queue.length > 0) {
    const currentNode = queue.shift();  // 큐에서 노드를 꺼냅니다.

    const neighbors = graph[currentNode];  // 현재 노드의 인접한 노드들을 가져옵니다.
    for (let i = 0; i < neighbors.length; i++) {
      const neighbor = neighbors[i];
      if (!visited.includes(neighbor)) {
        queue.push(neighbor);  // 방문하지 않은 인접한 노드를 큐에 넣습니다.
        visited.push(neighbor);  // 방문한 노드로 표시합니다.
      }
    }
  }
}

// 시작 노드 'A'에서 BFS를 실행합니다.
bfs('A');

BFS의 장점