DFS, BFS 파이썬으로 구현하기

백준 문제는 아니지만 개인적으로 공부하기 위해 DFS, BFS를 파이썬으로 구현했다.

https://itholic.github.io/python-bfs-dfs/

간단하게 잘 구현한 파이썬 코드가 있어 위 링크를 참조했다.

def bfs(graph, start_node):
    visit = list()
    queue = list()
    queue.append(start_node)
    while queue:
        node = queue.pop(0)
        if node not in visit:
            visit.append(node)
            queue=queue+graph[node]
    print(visit)
    return visit

bfs(graph, 'J')

하단은 내 코드, 최하단은 그 사람 코드

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H', 'K'],
    'K': ['J', 'L'],
    'L': ['K'],
    'M': ['H']
}

visit = list()
path = list()

def dfs(graph, start_node):
    visit.append(start_node)
    for item in graph[start_node]:
        if item not in visit:
            path.append(item)
            dfs(graph, item)

  1 def dfs(graph, start_node):
  2     visit = list()
  3     stack = list()
  4
  5     stack.append(start_node)
  6
  7     while stack:
  8         node = stack.pop()
  9         if node not in visit:
 10             visit.append(node)
 11             stack.extend(graph[node])
 12
 13     return visit

dfs(graph, 'B')
print(path)

Tech:

1. BFS는 FIFO인 queue를 이용해 방문하지 않은 노드들에 퍼져나가듯 적용한다.
2. DFS는 재귀를 타고 타고 타서 탈줄 조건에 도달하면 빠져나가는 식으로 구현한다.

그래프 탐색 알고리즘(DFS, BFS)

1. 경로 탐색 유형(최단거리, 시간)
2. 네트워크 유형(연결)
3. 조합 유형(모든 조합 만들기)

타겟 넘버, 네트워크, 단어변환, 여행경로와 같은 문제를 보면 DFS, BFS 중 하나를 떠올리면 ㅇㅋ