BFS와 DFS

어쩌다저쩌다, 코딩 초창기때 제대로 배우지 않고 넘어간 BFS(Breadth First Search) 너비우선탐색과 DFS(Depth First Search) 깊이우선탐색에 대해 블로깅을 하게 됬다. 확실히 개발을 처음 시작했을때는 탐색이라던지 트리라던지 다 왜 하는지도 잘 모르겠고 와닿지 않았지만, 시간이란 무섭다.. 어찌저찌 3년동안 개발이라는 분야에서 헐떡이다 보니 이전보다는 훨씬 와닿기 시작했다. (좋은 징조겠ㅈ.....)

DFS (깊이우선탐색)

말그대로 가능한 한 깊이 있는 노드까지 탐색을 진행한 후, 더 이상 갈 곳이 없으면 되돌아와서 다른 경로를 탐색하는 방식. 어떤 유튜브에서의 설명한 말을 빌려보자면, 넷플릭스 드라마 여러개를 볼 때, 한가지를 1화부터 끝까지 다 시청하고, 다른 드라마를 보는 방식.

탐색 방식: 깊이 우선
구현 방법: 재귀 호출 또는 스택 사용
용도: 경로 찾기, 사이클 탐지, 위상 정렬 등

python 코드:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited) #재귀호출
    return visited

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs(graph, 'A')

BFS (너비우선탐색)

노드에서 가까운 노드부터 탐색하는 것을 말한다. dfs처럼 한 우물만 파는 것이 아니라 우물1 파고, 우물2 파고, 우물3 파고... 마찬가지로 넷플릭스 드라마 여러개 중 한작품의 1화를 보고 다른 다른 한작품의 1화 보고.. 이런식이다. 내 스타일은 아닌듯하다. (안물 안궁 주의)

탐색 방식: 너비 우선
구현 방법: 큐 사용
용도: 최단 경로 탐색, 레벨 탐색, 최단 거리 문제 등

python 코드:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node)
        for next_node in graph[node]:
            if next_node not in visited:
                visited.add(next_node)
                queue.append(next_node)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')

reference:
https://www.youtube.com/watch?v=BsYbdUnKZ-Y

다음번엔 응용해서 문제풀이도 함께..