[Algorithm] 탐색 : 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)

<목차>

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

 

📁 DFS (Depth First Search) : 깊이 우선 탐색 / 스택 + 재귀

✔️ 최대한 멀리 있는 노드를 우선으로 탐색, 깊은 부분을 우선적으로 탐색

 

stack = [0, 1, 3, 4, 2, 5, 6]

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 
   • 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다. 
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

재귀함수는 수학의 점화식을 그대로 소스코드로 옮긴 형태이다.

데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다. 

 

✔️ python code

# 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) : 너비 우선 탐색 / 큐 + 반복

✔️ 모든 인접 노드를 탐색, 가장 가까운 노드부터 탐색

✔️ 두번 방문하지 않는다. 

 

queue = [0, 1, 2, 3, 4, 5, 6]

 

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

 

✔️ deque 라이브러리 사용

from collections import deque

 

탐색을 수행함에 있어 O(N)의 시간이 소요되며, 보통 DFS보다 BFS 구현이 조금 더 빠르게 동작한다. 

 

큐에 들어가는 순서대로 탐색 된다는 것에 주의하자. 

 

✔️ python code

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
  # 큐 구현을 위해 deque 라이브러리 사용
  queue = deque([start]) # 인자로 [start]가 들어간다는 것에 주의하자. int형을 인자로 넣을 수 없기 때문에 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)

 

---

Ref.

- 이것이 취업을 위한 코딩 테스트다 with 파이썬