DFS, BFS [Algorithm #1]

완전 탐색 방법이란, 모든 경우의 수를 따지는 것을 말한다. 단순한 편이고, 코테 현장에서 쉽게 떠올릴 수 있는 방법이다. 복잡도와 표본 수를 고려해야 하지만 대충 1억 회 이하는 충분히 사용이 가능하다고 한다. 

완전 탐색 방법에는 크게 두 가지가 있다.

1. DFS (Depth First Search) : 깊이 우선 탐색

시작 지점에서 가장 깊이 있는 노드를 우선 탐색하는 방식.
Stack을 이용하여 해결한다.
pop했을 때 방문하지 않은 인접 노드가 있으면 그 노드를 push한다.
다시 pop할 때 방금 push했던 노드가 무조건 먼저 pop되므로 가장 깊은 노드를 향해 탐색하게 된다.

 

재귀(Recursion)와 for문을 이용하여 작은 정점부터 깊이 우선 탐색을 수행하게 된다.

 

# 재귀를 이용한 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. BFS (Breadth First Search) : 너비 우선 탐색

시작 지점에서 최대한 넓게 우선 탐색하는 방식.
더 이상 탐색할 노드가 없을 때 한 단계 깊이 이동한다.
Queue를 이용하는데, collections 모듈에서 deque를 import하여 이용한다.

while문을 이용하여 queue가 빌 때까지 popleft와 append를 반복한다.

 

# deque를 이용, while문을 통해 queue가 빌 때까지 popleft,append를 반복
from collections import deque

def bfs(graph,v,visited):
  queue=deque([v])
  visited[v]=True
  while queue:
    t=queue.popleft()
    print(t, end=' ')
    for i in graph[t]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True

 

 

DFS와 BFS는 여러 정점이 있을 때, 작은 정점부터 방문하도록 하는 규칙이 대부분 문제에 적용되어 있다. 따라서 인접 리스트로 구현할 때 각 정점에 대한 인접 리스트에 대해 list.sort()를 수행하면 이를 해결할 수 있다.

 

추가로, list.sort()는 원본 list를 정렬하는 함수이고, sorted(list)는 원본 list는 건들지 않은 채로 정렬된 새로운 list를 반환하는 함수이다. 그래서 원본 리스트를 정렬하려고 할 때는 sort()를 써야 한다는 사실..

 

sorted(a)를 수행한 뒤, a는 정렬되지 않는 것을 확인할 수 있다.

 

언제 DFS / BFS를 써야 할까?

DFS와 BFS는 모든 정점을 탐색하는 알고리즘이므로 정점을 모두 방문해야 하는 문제에 적용할 수 있습니다.

그러나 DFS는 경로의 특징을 저장할 수 있으므로 특정 경로를 찾아야할 때 사용하고,

BFS는 너비를 우선 탐색하므로 최단 경로를 탐색할 때 사용하면 효율적으로 해결할 수 있습니다.