[22.01.22] BFS와 DFS 알고리즘

# 백준 문제를 풀다가 해당 알고리즘에 대한 이해가 우선인 것 같아 구글링을 통해 알고리즘 공부를 먼저 시작했다. 

 

# 참고자료

https://cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html

[Daily PS] 파이썬으로 구현하는 BFS와 DFS

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

 

- BFS ( Breadth First Search, 너비 우선 탐색 )

 

시작점인 루트노드에서 부터 인접한 노드를 우선적으로 방문한다.

 

큐(FIFO) 자료구조를 사용하는데 이 때 Python에서는 list타입에서 append와 pop명령을 사용할 수가 있는데 이렇게 되면 시간 복잡도가 O(N)으로 높기 때문에 시간적으로 비효율적인 코드가 만들어진다. 따라서 그냥 collections 라이브러리의 deque를 사용해주면 된다. 또한 인접 노드 중 방문하지 않았던 노드를 큐에 넣을 때는 set을 사용해주면 된다!

BFS, Wikimedia Commons

다음노드에 방문하고 방문한 노드에서 다음에 갈 수 있는 노드들을 queue에 넣고, 그 다음꺼 꺼내서 똑같은 방식 반복!! 

 

 

- DFS ( Depth First Search , 깊이 우선 탐색 ) 

 

루트 노드에서 다음 branch로 넘어가기 전에 해당 branch를 끝까지 탐색하는 방법

( wide 이전에 deep하게 탐색 )

 

스택(LIFO) 자료구조를 사용. BFS에 있던 큐 대신 스택을 사용해주면 된다. ( list가 스택 자료구조! )

BFS보다 간단한 대신 검색 속도가 더 느리다.

 

DFS, Wikimedia Commons

시작노드 1

1과 인접한 노드 방문 ( 위 그림에서 2,5,9 )

2 -> 5로 가기 전에 2의 이웃 노드를 모두 방문!

2를 시작으로 인접한 노드 방문 ( 이 때 노드가 여러개일 경우 처음 노드를 기준으로 deep )

하위 노드의 분기를 모두 탐색했다면 한 칸 위로 올라와 아직 방문이 안된 노드를 찾음

 

 

- Python 예시 구현코드 

from collections import deque

# BFS
def BFS_with_adj_list(graph, root): # graph는 딕셔너리(key:[value, value...]), root는 루트노드 
    visited = []
    queue = deque([root]) # 데크, 양방향 큐, 시간복잡도 O(1)

    while queue:
        n = queue.popleft() # 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 삭제
        if n not in visited:
            visited.append(n)
            # 가능한 다음 노드 중 이미 방문한 노드 삭제하고 que에 추가
            queue += graph[n] - set(visited)
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))

# DFS
def DFS_with_adj_list(graph, root):
    visited = []
    stack = deque([root])

# 일반적인 트리구조를 뒤집은 형태로 알고리즘이 돌아간다고 생각하면 된다. ( pop 때문 )
    while stack:
        n = stack.pop() # 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 삭제
        if n not in visited:
            visited.append(n)
            # 가능한 다음 노드 중 이미 방문한 노드 삭제하고 stack에 추가
            stack += graph[n] - set(visited)  
    return visited

print(DFS_with_adj_list(graph_list, root_node))

 

기본적인 알고리즘에 대해서는 이해했고 추후에 백준 문제들을 풀어보며 익숙해져야 할 것 같다.