DFS와 BFS

  DFS(Depth-first search)와 BFS(Breadth-first search) 그래프나 트리 구조의 탐색방법으로 dfs는 한 노드를 깊숙하게 탐색한 다음 다시 돌아가서 다음 노드를 탐색하는 방식, bfs는 자식 노드를 stack 에 저장한 다음 차례대로 탐색하는 방식이다.

DFS와 BFS 탐색 방식 출처 : Wikimedia Commons 

    dfs를 활용할 때는 재귀함수에 대한 이해가 있어야 하고 bfs를 활용할 때는 queue에 대한 이해가 필요하다.  

트리 구조 출처 : favtutor

# Using a Python dictionary to act as an adjacency list
graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node):  #function for dfs 
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')

  트리 구조형태의 자료를 탐색하고자 할 때, 방문 여부를 기록하는 visited를 set()으로 설정했고,  dfs함수를 설정 현재 node를 방문한 적이 없었을 경우, node를 출력하고 node를 visited에 기록한다. node에서 연결된 node중 숫자가 가장 낮은 node부터 재귀적으로 탐색하기 위해 dfs(visited, graph, neighbor)을 반복한다. 위 트리 구조를 dfs 로 탐색할 경우, 출력결과는 5, 3, 2, 4, 8,  7이 된다. 5부터 방문하고 5부터 연결된 3을 방문하고 3에서 연결된 2를 방문 하는 식으로 반복된다. 

 

graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

visited = [] # List for visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node): #function for BFS
  visited.append(node)
  queue.append(node)

  while queue:          # Creating loop to visit each node
    m = queue.pop(0) 
    print (m, end = " ") 

    for neighbour in graph[m]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
print("Following is the Breadth-First Search")
bfs(visited, graph, '5')    # function calling

  bfs의 경우에는 현재node의 child node를 저장하기 위해 queue를 하나 만들었고, node를 visited와 queue에 저장한다. bfs는 stack저장 한 것이 없을때 까지 탐색하기 때문에 while 문으로 queue 존재여부를 확인했다. FIFO 방식이기 때문에 queue.pop(0)으로 node.value를 꺼내오고 자식 노드를 순서대로 방문하면서 queue에 순서대로 저장한다. 자식 노드들을 전부 저장했으면 다시 while로 돌아가 첫번째로 저장했던 자식노드에 대해서 방문과 자식노드 여부를 확인한다.  출력결과는 5, 3, 7, 2, 4, 8이 된다.

 

  dfs로 풀리는 문제들은 거의 bfs로 풀수 있다.  dfs와bfs문제는 코딩테스트에 자주 출제되는 영역으로 확실하게 짚고 넘어가야 하는 부분이다.  recursive와 stack ,queue개념을 알아야 직접 구현할 수 있기 때문에 어려울 수도 있지만 익숙해지기 위해서 많은 문제를 풀면서 연습해야겠다.