[알고리즘] 깊이우선탐색(DFS)과 너비우선탐색(BFS)

 

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

해당 블로그의 글이 깔끔하게 정리되어있어 그대로 가져왔습니다. 좀더 상세한 사항은 해당블로그를  참조.

깊이우선탐색(DFS / Depth First Search) 

너비우선탐색(BFS / Breadth First Search)

 

▶ 해당 개념을 알기 위해서는 세 가지의 개념이 선행되어야 한다.

1) 먼저 자료구조 스택/큐 이해가 필요하다.
스택/큐에 대한 설명은 아래 링크에 따로 정리했다.
👉🏻 https://velog.io/@falling_star3/자료구조-스택Stack큐Queue덱Deque

2) 재귀함수의 호출과 리턴 과정에 대한 이해가 필요하다.
재귀함수에 대한 설명은 아래 링크에 따로 정리했다.
👉🏻 https://velog.io/@falling_star3/Python-재귀함수Recursive-Function

3) 간선과 노드 및 인접행렬과 인접리스트에 대한 그래프 이해가 필요하다.
그래프에 대한 설명은 아래 링크에 따로 정리했다.
👉🏻 https://velog.io/@falling_star3/그래프Graph-인접행렬과-인접리스트

4) BFS/DFS를 처음 접하는 사람은 아래 링크의 유튜브 설명을 보는 것을 추천한다.
BFS/DFS를 이해하기 정말 좋은 영상이고, 이 포스팅도 해당영상을 기반으로 했다.
👉🏻 https://www.youtube.com/watch?v=_hxFgg7TLZQ

 

▶ 위의 그림은 DFS와 BFS 경로를 순서대로 나타낸 것이다.

해당 그림을 통해 직관적으로 DFS와 BFS의 차이를 알 수 있을 것이다.
깊이우선탐색인 DFS는 가장 깊은 곳까지 방문하고, 너비우선탐색인 BFS는 같은 레벨 인접 노드를 전부 방문한뒤 다음 레벨 인접 노드를 방문한다. DFS는 Stack을 통해 구현하고, BFS는 Queue를 통해 구현한다.

---

✏️ 깊이우선탐색(DFS) 구현

 

👉🏻 깊이우선탐색 DFS(Depth-First Search)는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

▶ 깊이우선탐색(DFS) 구현 방법

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

▶ 해당 그래프를 DFS로 구현해보자. DFS는 Stack을 이용한다. Stack은 한 방향에서만 자료를 넣고 뺄 수 있는 후입선출 방식 구조이므로, 가장 늦게 들어온 노드를 가장 먼저 뺄 수 있다. 또한, 한 번 담았던 노드는 다시 담지 않는다.

▶ 먼저 시작 노드인 0번 노드를 스택에 담았다.

▶ 이 후 0번 노드를 꺼내 출력하고, 그 인접 노드인 1번 노드를 스택에 담았다.

▶ 이 후 1번 노드를 꺼내 출력하고, 그 인접 노드인 2번 노드와 3번 노드를 스택에 담았다.

▶ 이 후 3번 노드를 꺼내 출력하고, 그 인접 노드인 4번 노드와 5번 노드를 스택에 담았다.
    2번 노드는 이미 스택에 담겨있으므로 스택에 다시 추가하지 않는다.

▶ 이 후 5번 노드를 꺼내 출력하고, 그 인접 노드인 6번 노드와 7번 노드를 스택에 담았다.

▶ 이 후 7번 노드를 꺼내 출력하고, 인접 노드가 없으므로 더 담지 않는다.

▶ 이 후 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 스택에 담았다.

▶ 이 후 8번 노드를 꺼내 출력하고, 인접 노드가 없으므로 더 담지 않는다.

▶ 이 후 4번 노드를 꺼내 출력하고, 2번 노드를 꺼내 출력한다. 더 꺼낼 노드가 없으므로 순회는 종료한다.

 

DFS 경로 : 0 > 1 > 3 > 5 > 7 > 6 > 8 > 4 > 2

 

💡 출력 순서와 과정은 스택이기 때문에 위와 같이 이루어지는 것이다. 스택은 마치 박스 쌓기와 같아서 가장 늦게 올린 박스를 가장 먼저 꺼낼 수 있다. DFS 구현 과정 또한 스택으로 구현하는 것이기에 가장 위에 있는 노드를 계속 꺼내는 것이다.

---

✏️ 너비우선탐색(BFS)

 

👉🏻 BFS(Breadth First Search)는 그래프에서 가까운 노드부터 탐색하는 알고리즘이다.

 

▶ 너비우선탐색(BFS) 구현 방법

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

▶ 해당 그래프를 BFS로 구현해보자. BFS는 Queue를 이용한다. Queue는 가장 먼저 들어온 것이 가장 먼저 나가는 선입선출 방식의 구조이다. DFS 구현과 마찬가지로 한번 큐에 담았던 노드는 다시 담지 않는다.

▶ 먼저 시작 노드인 0번 노드를 큐에 담았다.

▶ 이 후 0번 노드를 꺼내 출력하고, 그 인접 노드인 1번 노드를 큐에 담았다.
    큐는 선입선출이므로 꺼내는 방향이 그림의 화살표처럼 아래부터이다.

▶ 이 후 1번 노드를 꺼내 출력하고, 그 인접 노드인 2번 노드와 3번 노드를 큐에 담았다.

▶ 이 후 2번 노드를 꺼내 출력하고, 그 인접 노드인 4번 노드를 큐에 담았다.

💡 큐는 선입선출 방식이므로 가장 아래 있는 2번 노드부터 꺼낸다. 또한, 그 인접 노드 중 1번, 3번은 이미 큐에 들어갔었으므로 4번 노드만 큐에 담긴다.

▶ 이 후 3번 노드를 꺼내 출력하고, 그 인접 노드인 5번 노드를 큐에 담았다.

▶ 이 후 4번 노드를 꺼내 출력하고, 그 인접 노드는 전부 큐에 담았던 적이 있으므로 다시 담지 않는다.

▶ 이 후 5번 노드를 꺼내 출력하고, 그 인접 노드인 6번 노드와 7번 노드를 큐에 담았다.

▶ 이 후 6번 노드를 꺼내 출력하고, 그 인접 노드인 8번 노드를 큐에 담았다.

▶ 이 후 7번 노드를 꺼내 출력하고, 8번 노드를 꺼내 출력한다. 더 꺼낼 노드가 없으므로 순회는 종료한다.

 

BFS 경로 : 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8

---

✏️ DFS와 BFS 예제

백준에서 대표문제인 1260번 DFS와 BFS예제가 있다.
아래 링크에 해당 문제와 구현을 자세히 적어놨다.
https://velog.io/@falling_star3/백준Python-1260번-DFS와BFS

 

▶ 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]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

dfs(graph, 1, visited)

# 출력
1 2 7 6 8 3 4 5

위와 같이 과정이 이루어진다.

▶ 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(graph, 1, visited)

# 출력
1 2 3 8 7 4 5 6 

위와 같이 과정이 이루어진다.