[DFS/BFS 알고리즘] 탐색 알고리즘 DFS/BFS

탐색 (Search)

- 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미

- 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸

 

그래프 (Graph)

- 그래프는 노드와 간선으로 표현됨

- 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말함

- 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'라고 표현

- 그래프는 크게 2가지 방식으로 표현할 수 있음

 

인접 행렬 (Adjacency Matrix)

- 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

- 파이썬에서는 2차원 리스트로 인접 행렬을 구현할 수 있음

- 연결이 되어 있지 않은 노드끼리는 무한의 비용(INF)라고 작성

- 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비

 

인접 리스트 (Adjacency List)

- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장

- '연결 리스트'라는 자료구조를 이용하여 구현

- 파이썬으로 인접 리스트를 이용하여 그래프를 표현하고자 할 때에도 단순히 2차원 리스트를 이용하면 됨

- 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용

- 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림

- 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우, 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적음

 

DFS (Depth First Search)

- 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘

- 스택 자료구조를 이용하여 구현이 간단

- 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어 데이터의 개수가 N개인 경우 O(N)의 시간이 소요

- 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀 함수를 이용하였을 때 매우 간결하게 구현할 수 있음

구체적인 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 함. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

 

# DFS 함수 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

BFS (Breath First Search)

- 너비 우선 탐색이라는 의미, 쉽게 말해 가까운 노드부터 탐색하는 알고리즘

- 선입선출 방식인 큐 자료구조를 이용하는 것이 정석 (큐 자료구조에 기초한다는 점에서 구현이 간단)

- 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 나가게 되어, 가까운 노드부터 탐색을 진행하게 됨

- deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요

- 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편

 

정확한 동작 방식

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 함

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

 

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)