[Algorithm] DFS, BFS

* Python을 기준으로 합니다

---

DFS (Depth-First Search), BFS (Breadth-First Search)

- 개념

• DFS (깊이 우선 탐색), BFS (너비 우선 탐색) : 그래프의 모든 노드를 한 번씩 방문하는 그래프 순회 작업을 위한 알고리즘
  • 완전 탐색과 같이 탐색 방향을 결정하고, 다음 탐색의 유효성을 검사해야 하는 경우 사용
  • 방문 처리 : 그래프에서 한번 처리되어 탐색된 노드가 다시 탐색되지 않게 체크하는 과정
• DFS : 스택, 재귀로 주로 구현됨
  • 그래프에서 더 이상 탐색할 노드가 없을 때까지 진행한 다음, 탐색할 노드가 없으면 가장 최근의 방문 노드로 돌아가 다른 노드를 탐색하는 방법
    
  • DFS의 동작 과정
    1. 스택에 시작 노드를 push
    2. 스택이 비어있다면 탐색을 종료
    3. 비어있지 않다면 스택에서 노드를 pop 하고, 해당 노드의 방문 여부를 확인
       - 방문하지 않은 노드면 방문 처리함
    4. 방문한 노드와 인접한 다른 모든 노드를 확인함
       - 방문하지 않은 노드가 있다면 스택에 push
    5. 위 2~4 과정을 반복

DFS의 동작 과정 1

DFS의 동작 과정 2

• BFS : 큐를 활용하여 구현됨
  • 그래프에서 시작 노드와 가장 가까운 노드들부터 방문하여 탐색하는 방식
  • BFS의 동작 과정
    1. 큐에 시작 노드를 push 하고 방문 처리함
    2. 큐가 비어있다면 탐색을 종료
    3. 비어있지 않다면 큐에서 노드를 pop 한 다음, 해당 노드와 인접한 노드들 중에서 방문하지 않은 노드를 큐에 push 하고 방문 처리함
    4. 위 2~3번 과정을 반복

BFS의 동작 과정 1

BFS의 동작 과정 2

• DFS vs. BFS
  • DFS는 한 방향으로 계속 탐색한 후 다시 돌아오는 특징 (백트래킹)이 있고, BFS는 가중치가 없는 그래프에서 최단 경로를 보장함 
    - 탐색 문제에서 최단 경로가 아닌 대부분의 경우 DFS를 고려하는 것이 유리
    - 최단 경로 문제의 경우 BFS를 고려하는 것이 유리
  • 방문 처리 방식의 차이
    - DFS는 스택에 다음에 방문할 인접 노드를 push 한 다음, pop 할 때 방문 처리
    - BFS는 큐에 방문할 노드를 push 하면서 방문 처리

- 구현

1. DFS의 구현

• DFS는 기본적으로 스택을 활용하여 구현함

def DFS_stack(graph, visited, start): #스택 DFS
  stack = [] #스택 선언
  stack.append(start) #스택에 시작노드 push

  while stack: #스택에 값이 있다면 계속 반복
    node = stack.pop() #스택에서 값을 pop
    if node not in visited: #pop한 노드가 방문하지 않은 노드이면
      visited.append(node) #방문처리
      for i in graph[node]: #해당 노드의 인접 노드들을
        stack.append(i) #스택에 push
  
  return visited

• 재귀를 활용하여 DFS를 구현할 수도 있음

def DFS_recur(graph, visited, start): #재귀 DFS
  visited.append(start) #현재노드 방문처리

  #현재 노드와 인접한 다른 노드들을
  for i in graph[start]:
    if i not in visited: #방문하지 않았다면
      visited = DFS_recur(graph, visited, i) #recursion
  
  return visited

• DFS 결과 확인
  • 스택 DFS와 재귀 DFS의 방문 순서가 다름
  • 재귀 방식은 오름차순으로 방문하고 스택 방식은 내림차순으로 방문함
    - 스택은 LIFO 구조로 인해 push 된 인접 노드들 중에서 가장 마지막부터 방문하기 때문

#인접 리스트 형식 그래프 표현
graph = {
    1:[2,3,8],
    2:[1, 7],
    3:[1,4,5],
    4:[3,5],
    5:[3,4],
    6:[7],
    7:[2,6,8],
    8:[1,7]
}

#stack DFS
visited = [] #방문처리 용
print(DFS_stack(graph, visited, 1)) #[1, 8, 7, 6, 2, 3, 5, 4]

#recursive DFS
visited = [] #방문처리 용
print(DFS_recur(graph, visited, 1)) #[1, 2, 7, 6, 8, 3, 4, 5]

2. BFS의 구현

• BFS는 큐를 활용하여 구현함

import collections #큐 사용 위함

def BFS(graph, visited, start):
  queue = collections.deque() #큐 선언
  
  queue.append(start) #큐에 시작 노드 push하고
  visited.append(start) #방문처리 

  while queue: #큐에 값이 있을 동안 반복
    node = queue.popleft() #큐에서 노드를 pop하고 
    for i in graph[node]: #해당 노드와 인접한 노드들 중에서
      if i not in visited: #방문하지 않은 노드를 
        queue.append(i) #큐에 push
        visited.append(i) #방문처리

  return visited

• BFS 결과 확인

#인접 리스트 형식 그래프 표현
graph = {
    1:[2,3,8],
    2:[1, 7],
    3:[1,4,5],
    4:[3,5],
    5:[3,4],
    6:[7],
    7:[2,6,8],
    8:[1,7]
}

visited = [] #방문처리용
print(BFS(graph, visited, 1)) #[1, 2, 3, 8, 7, 4, 5, 6]