[알고리즘] 완전탐색 DFS & BFS

깊이 우선 탐색 (DFS)

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

 

깊이 우선 탐색(DFS)은 스택 자료구조(또는 재귀 함수)를 이용한다.

 

완전탐색 방법 중 하나로 모든 경우의 수를 확인해야 할 경우 사용한다.

 

예를 들어 모든 조합을 확인하여 특정 조합의 개수를 구하는 문제를 풀 때 사용할 수 있다.

 

DFS 탐색 방법

1번 노드부터 시작
접근하지 않은 노드가 있다면 번호가 낮은 노드부터 접근하여 PUSH

 

PUSH(1) -> PUSH(2) -> PUSH(7) -> PUSH(6)
Stack = [1, 2, 7, 6]

 

다음 노드가 없을 경우 접근하지 않은 노드가 연결된 노드가 나올 때까지 POP

 

POP(6)
Stack = [1, 2, 7]

 

이 과정을 반복하면 탐색 순서는

 

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

 

코드

이를 Python 코드로 구현하면 다음과 같다.

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

graph=[
  [],# 0번 노드
  [2, 3, 8],#1번 노드에 연결되어 있는 인접노드들
  [1,7],#2번 노드에 연결되어 있는 인접노드들
  [1,4,5],#3번 노드
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

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

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

 

---

너비 우선 탐색 (BFS)

BFS는 너비 우선 탐색이라고 부르며 그래프에서 가까운 부분부터 우선적으로 탐색하는 알고리즘이다.

너비 우선 탐색(BFS)는 큐 자료구조를 이용한다.

 

이 또한 완전탐색방법 중 하나이며, DFS와 다른 점은 모든 경우의 수를 다 확인할 필요가 없다는 점이다.

 

예를 들어 원하는 조합 하나를 찾아야 할 때 해당 조합이 마지막에 있다면 전부 조합해봐야 한다.

하지만 그게 아니라면 해당 조합을 찾았을 때, 나머지는 굳이 찾을 필요가 없기 때문에 이 경우에는 BFS를 사용해주는 것이 좋다.

 

즉, 문제를 확인하고 해당 문제에 맞는 알고리즘을 선택하는 것이 중요하다.

 

BFS 탐색 방법

1번 노드부터 큐에 삽입한 후 방문 처리

Enqueue(1)
QUEUE = [1]

 

큐에서 1번 노드를 꺼내 1번노드에서 방문되지 않은 인접노드들을 큐에 삽입 후 방문처리

Dequeue(1) -> Enqueue(2) -> Enqueue(3) -> Enqueue(8)
QUEUE = [2, 3, 8]

 

2번 노드를 큐에서 꺼내어 2번노드에서 방문되지 않은 인접노드들을 삽입 후 방문처리

Dequeue(2) -> Enqueue(7)
QUEUE = [3, 8, 7]

 

그 다음은 3번 노드를 꺼내 3번노드 기준으로 방문하지 않은 인접노드들을 방문한다.

이 과정을 반복하면 탐색 순서는

1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

 

 

코드

이를 Python으로 구현하면 다음과 같다.

from collections import deque

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


graph=[
  [],# 0번 노드
  [2, 3, 8],#1번 노드에 연결되어 있는 인접노드들
  [1,7],#2번 노드에 연결되어 있는 인접노드들
  [1,4,5],#3번 노드
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

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

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