[Algorithm] 너비우선탐색(BFS), 깊이우선탐색(DFS)

배울 때마다 헷갈리고 이해되지 않던 우선 탐색들... 오늘 드디어 완전히 이해 완료했다 생각보다 간단한 원리로 제작!

그래프로 문제를 해결할 때 어떤 방식으로 해결해야 적절한지에 따라 갈린다. 알고리즘에 큰 차이는 없다!

 

너비 우선 탐색 (Breadth First Seartch)

말 그대로 '너비를 우선적으로 탐색하는 알고리즘'이다.

즉, 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문한다고 생각하면 쉽다.

'큐(queue)'를 사용하는 것이 이 알고리즘의 핵심!

노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣어 '먼저 큐에 들어있던 순서대로' 노드를 방문하면 된다.

이때, python 라이브러리 중 deque 를 사용하면 시간을 절약할 수 있다.

 

코드

from collections import deque

def bfs(graph, start_node):
    visit = []  #이미 방문한 노드
    queue = deque([start_node])  #첫 노드부터 시작

    while queue:  #모두 방문했을 때까지
        node = queue.popleft()  #맨 앞에 있는, 그러니까 이전 노드와 연결된 맨 윗 순서부터 방문 시작
        if node not in visit:  #아직 방문하지 않았다면
            visit.append(node)  #방문 완료
            queue.extend(graph[node])  #지금 노드와 연결된 노드들 추가

    return visit

 

깊이 우선 탐색 (Depth First Search)

말 그대로 '깊이를 우선적으로 탐색하는 알고리즘'이다.

즉, 루트 노드부터 갈 수 있는 끝까지 탐색해 최하단의 노드를 방문하고, 모두 방문했으면 다시 그 다음 길의 노드를 방문하는 식으로 탐색하는 것이다.

'스택(stack)'을 사용하는 것이 이 알고리즘의 핵심!

현재 방문한 노드에서 연결된 노드를 방문해야만 한 방향으로 쭉 이어나갈 수 있기 때문이다.

 

코드

def dfs(graph, start_node):
    visit = []  #이미 방문한 노드
    stack = [start_node]  #첫 노드부터 시작

    while stack:  #모두 방문했을 때까지
        node = stack.pop()  #맨 뒤에 있는 노드부터, 즉 현재 노드와 바로 연결된 노드들부터 쭉 탐색
        if node not in visit:  #아직 방문하지 않았다면
            visit.append(node)  #방문 완료
            stack.extend(graph[node])  #지금 노드와 연결된 노드들 추가

    return visit