[알고리즘] BFS와 DFS을 구현해보자!

이번 포스팅에서는 알고리즘을 공부하면서 출제 빈도가 높은 BFS와 DFS 문제를 위한 기본 구현을 정리하려고 한다.

 

BFS와 DFS는 이름에서부터 알 수 있듯 그래프 탐색 알고리즘이다. 탐색 알고리즘은 그래프 전체를 순회해야 하는 고비용 연산으로 효율적으로 코드를 짜는 것이 중요하다.

 

BFS와 DFS 모두 시간 복잡도는 동일하다. 그래프는 인접 행렬과 인접 리스트 자료구조를 이용해 표현이 가능한데, 어떤 자료구조를 사용하느냐에 따라 시간 복잡도가 아래와 같이 달라진다. (V = Vertex, E = Edge)

 

• 인접 행렬: O(V^2)
• 인접 리스트: O(V+E)

 

최소 비용 문제나 이동에 가중치가 없는 미로탐색 문제는 BFS로 푸는 것이 유리하고, 이동에 제약이 있거나 이동마다 가중치가 붙는 미로탐색 문제는 DFS로 푸는 것이 유리하다. 그 이유는 DFS가 탐색 시간은 더 걸려도 가중치에 대한 변수를 지속적으로 관리할 수 있어 코드 구현 시 편리하기 때문이다.

 

 

이제 BFS와 DFS를 구현해보자.

 

일단 기본적으로 BFS는 Queue를 이용해서 풀 수 있고 DFS는 재귀함수 또는 Stack을 이용해서 풀 수 있다. DFS는 어떤 방법으로 구현하든 큰 차이가 없기 때문에 각자 편한 방법을 택하면 된다. 하지만 재귀함수를 이용하면 콜스택을 나오면서 return 값을 이용해 호출의 역방향으로 어떤 연산이 가능하기 때문에 이를 활용해 문제를 풀 수 있다. 예를 들어 트리의 leaf 노드에서부터 어떤 값을 채워나가면서 root 노드의 값을 계산해야 하는 경우 재귀함수 DFS를 사용할 수 있는 것이다.

그래프에 cycle이 있는 경우, 탐색을 완료한 노드를 체크를 통해 중복 체크와 무한 루프를 방지해야 한다.

 

BFS

import collections as c

def bfs(v, graph):
    queue = c.deque()
    queue.append(v)
    visited = set()

    while queue:
        a = queue.popleft()

        if a in visited: continue

        print(a, end=" ")
        visited.add(a)

        if graph.get(a):
            [queue.append(i) for i in sorted(graph[a])]

 

 

DFS

스택 사용

def dfs(v, graph):
    stack = [v]
    visited = set()

    while stack:
        a = stack.pop()

        if a in visited: continue

        print(a, end = " ")
        visited.add(a)

        if graph.get(a):
            stack.extend(sorted(graph[a], reverse=True))

재귀함수 사용 (1)

def dfs(v, graph, visited):
    if v in visited: return
    
    print(v, end = " ")
    visited.add(v)
    
    # 자식 노드가 있을 때
    if graph.get(v):
        for c in graph[v]:
            dfs(c, graph, visited)

재귀함수 사용 (2) - return 값을 이용해서 호출의 역방향으로 연산

def dfs(v, graph, visited):
    # 방문한 노드일 때
    if v in visited: return 0
    
    visited.add(v)
    
    # leaf 노드일 때
    if not graph.get(v): return 1
        
    total = 0
    for c in graph[v]:
        total += dfs(c, graph, visited)
      
    return total