[ST_A] 알고리즘 정리 - DFS와 BFS (feat.자료구조)

DFS와 BFS를 공부하기 전에 자료구조를 살짝 들여다보자.

자료구조의 정의는 아래와 같다.

무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법

익숙한 자료구조로는 Stack, Queue, Tree, Graph 등이 있다.

Stack

• LIFO (last in, first out) / 후입선출 (가장 늦게 들어온 것부터 먼저 나간다)
• 회전 초밥 집에 쌓인 접시처럼 생겼다.

Queue

• FIFO (first in, first out) / 선입선출 (가장 먼저 들어온 것부터 먼저 나간다)
• 톨게이트를 그려보면 쉽게 이해가 된다.

Graph

• 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조
• 방향성을 가진다: 무방향 / 단방향
• 진입차수 / 진출차수: 정점에 들어오는 간선의 수 / 정점에서 나가는 간선의 수
• 자기루프: 정점에서 나간 간선이 곧바로 진입하는 경우
• 사이클: 서울 → 대전 → 부산 → 서울

Tree

• 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한 자료 구조
• 노드: 모든 개별 데이터
• 루트: 트리 구조의 시작
• 부모 노드: 상하 관계의 두 노드 중 루트에 가까운 노드
• 자식 노드: 상하 관계의 두 노드 중 루트에 먼 노드
• 리프 노드: 트리 구조의 끝 노드(자식 구조가 없는 노드)

탐색

탐색은 다양한 알고리즘을 적용하기 좋은 테마 중 하나이다.
추상적일 수 있지만 우리가 맞이하는 다양한 문제 등을 탐색을 통해 해결할 수 있다.
미로게임이, 로봇청소기, 최단 거리 또는 최단 시간 경로 찾기 등이 탐색을 통해서 문제를 해결해 볼 수 있다.

탐색에도 여러 방법이 있겠지만
오늘은 tree, stack, queue 등의 자료구조를 통해 DFS와 BFS를 다루어 보기로 한다.

BFS (Breath-First Search)

• 너비 우선 탐색
• 노드 레벨 순서에 따라 순회:
  부모 노드 기준으로 바로 자신의 자식 노드 레벨(또는 인접 노드)을 모두 살피고 해당 자식 노드들의 바로 아래의 자식 노드 레벨(또는 인전 노드)을 탐색한다.
• 자료구조 Queue를 활용하여 문제 해결할 수 있다.
• 최단 경로를 알아내야 하는 경우 또는 찾아야 하는 노드가 인접한 경우 사용한다.

Javascript로 구현한 BFS 문제 풀이이다.

const bfs = (graph, start, visited = []) => {
  let queue = [start]
  visited.push(start)

  while (queue.length > 0) {
    node = queue.shift()
    for (value of graph[node]) {
      if (!visited.includes(value)) {
        queue.push(value)
        visited.push(value)
      }
    }
  }
  return visited
}

const graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

bfs(graph, 1)
// [ 1, 2, 3, 8, 7, 4, 5, 6 ]

DFS(Depth-First Search)

• 깊이 우선 탐색
• 연결되어 있는 노드를 우선하여 순회:
  부모 노드 기준으로 자신의 자식 노드 중 하나를 탐색하고 해당 자식 노드의 자식 노드를 탐색하는 순서로 탐색한다.
• 자료구조 stack과 재귀를 활용하여 문제 해결할 수 있다.
• 경로를 완벽하게 탐색해야 할 때 사용한다.

Javascript로 구현한 DFS 문제 풀이이다. Stack과 재귀를 활용하였다.

const dfs_recussion = (graph, start, visited=[]) => {
  visited.push(start);
  for (node of graph[start]) {
    if (!visited.includes(node)) {
      dfs_recussion(graph, node, visited)
    }
  }
  return visited
}

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

dfs_recussion(graph, 'A')
// [ 'A', 'B', 'D', 'E', 'F', 'C', 'G', 'H' ]

두 알고리즘의 Tree 탐색 경로를 비교해보자