[Algorithm] DFS/BFS 알고리즘 정리

알고리즘 1도 모르던 시절, DFS와 BFS는 주변에서 너무나 많이 언급한 탓에 익히 들었던 알고리즘이다.

그만큼 코테에서 많이 등장하는 알고리즘이다. 

처음 알고리즘 배울 때 개념은 이해가 되는데 막상 구현하려고 하면 너무나 헷갈렸던 기억이 난다.

그래서 이제 두번 다시 헷갈릴 일 없도록 마지막으로!!! 확실히 개념을 정리하고 넘어가려고 한다.

 

 

 

 

DFS 

우선, DFS(Depth First Search)는 직역한 그대로 '깊이 우선 탐색' 알고리즘이다. 그래프에서 깊은 부분을 우선적으로 탐색한다. DFS 구현 코드는 아래와 같다.

 

# DFS 메소드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end='')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 방문여부를 기록하기 위한 배열 선언
visited = [False]*9

# 정의된 DFS 함수 호출
dfs(graph,1,visited)

 

DFS의 핵심은 바로 '재귀'와 '스택'이다. 타깃 노드를 기준으로 해당 노드와 연결된 다른 노드를 탐색하고, 또 그 노드와 연결된 다른 노드를 계속해서 탐색한다. 이때 dfs 함수를 재귀적으로 호출하는 방식으로 탐색을 한다. 만약 탐색한 노드들이 이미 방문된 노드들이라면, 다시 또 새로운 노드를 타깃으로 잡아 그 노드와 연결된 노드들을 모두 탐색한다. 스택은 선입후출이다. 즉 마지막에 들어온 노드가 가장 먼저 나가게 되는 것인데, 딱 DFS를 구현하기 알맞은 도구이다.

 

 

 

 

구현한 코드를 그림으로 나타내봤다.

 

DFS 구현 코드 동작 모습

 

이런 식으로 하나의 노드를 잡고 그 노드와 이어진 노드들을 깊이 판다. 딱 깊숙이 파는 느낌!

 

 

 

 

 

 

BFS

BFS(Breadth First Search)는 '넓이 우선 탐색' 알고리즘이다. 단어 그대로 넓이를 우선적으로 탐색하는 것이다. 기준이 되는 노드와 가까운 노드부터 탐색한다. DFS가 최대한 멀리 있는 노드까지 우선적으로 탐색한다면, BFS는 그 반대로, 최대한 인접한 노드 먼저 탐색한다. 이때 BFS의 핵심은 바로 '큐'를 이용하는 것이다. 큐는 선입선출이다. BFS는 선입선출을 활용하기에 알맞은 알고리즘이다. 그리고 이때 큐는 파이썬에서 제공하는 deque를 사용하는 것이 좋다고 한다. 탐색 시간이 O(N)이라서! 아래는 BFS 구현 코드이다.

 

from collections import deque

# BFS 메소드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 원소 하나씩 뽑아 출력
        v = queue.popleft()
        print(v, end='')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True



# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 방문여부를 기록하기 위한 배열
visited = [False]*9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

 

가장 먼저 들어온 노드를 popleft를 이용해 꺼내고, 꺼낸 노드와 인접한 노드를 큐에 넣는다. 그리고 그 다음으로 먼저 들어온 노드를 popleft로 꺼내서 이와 인접한 노드를 또 다시 큐에 넣는다. 이런식으로 큐가 빌 때까지 계속 반복한다. 얘는 재귀말고 while문을 사용한다.

 

 

아래는 구현한 코드를 그림으로 표현해본 것

 

 

 

 

 

 

그리고 '이것이 코딩테스트다' 읽으면서 알게된 것인데, 일반적으로 BFS를 구현하는게 DFS보다 수행시간이 빠르다고 한다! 역시 DFS가 재귀를 써서 그런가.... 

 

DFS와 BFS는 알고리즘을 공부한 사람이라면 몰라서는 안되는 개념이기 때문에 이것만큼은 제대로 구현할 수 있을 정도로 코드를 익혀두는 것이 좋겠다!