[알고리즘] DFS & BFS

대표적인 탐색 알고리즘

• 탐색이란 "원하는 데이터를 찾는 과정"을 의미함
• 스택, 큐, 재귀 함수는 DFS와 BFS에서 가장 중요한 개념이다.

DFS (Depth-First Search)

• 깊이 우선 탐색
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조를 이용
• 모든 노드를 방문하고자 할 때 주로 사용

동작 과정

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)

# 출력: 1 2 7 6 8 3 4 5

BFS (Breadth-First Search)

• 너비 우선 탐색
• 가까운 노드부터 탐색하는 알고리즘
• 큐 자료구조 이용
• 보통 최단 경로 문제에서 많이 사용

동작 과정

1. 탐색 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행 할 수 없을 때까지 반복한다.

구현

파이썬의 경우 deque 라이브러리를 이용해 구현 가능

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현 위해 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)

# 출력: 1 2 3 8 7 4 5 6

---

💡 DFS & BFS 를 이해하기 위해서는 그래프에 대해서 알아야 한다!

그래프 기본 구조

그래프는 노드(Node)와 간선(Edge)으로 표현됨

• 노드 : 정점(Vertex)이라고도 함
• '두 노드는 인접하다' : 두 노드가 간선으로 연결되어 있다.

그래프 탐색

하나의 노드를 시작으로 다수의 노드를 방문하는 것

그래프 표현 방식

• 인접 행렬(Adjacency Matrix)

  • 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  • 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비됨

• 인접 리스트(Adjacency List)

  • 리스트로 그래프의 연결 관계를 표현하는 방식
  • 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용
  • 연결된 데이터를 하나씩 확인해야 하기 때문에 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림