DFS/BFS (탐색 알고리즘)

DFS/BFS(탐색 알고리즘)

DFS(Depth-First-Search)는 가장 깊은 부분을 우선적으로 탐색하는 알고리즘이고 BFS(Breadth-First-Search)는 가장 가까운 노드부터 탐색하는 알고리즘이다.

[DFS]

‘가장 깊은 부분을 우선적으로 탐색하는 알고리즘’ 텍스트 자체만 읽으면 헷갈리거나 어려울 것 없다.
하지만, 데이터의 구조가 어떻길래 깊은 부분이 있지? 라고 생각할 수가 있다. 
DFS는 바로 그래프 즉, 노드와 노드를 연결하여 모아둔 비선형 자료구조를 탐색할 때 사용하는 알고리즘이다.

그래프

그래프는 위와 같은 형태를 하고 있으며 한 번쯤은 들어봤을 법한 데이터 구조인 트리구조 역시 그래프의 일종이다. 이런 그래프는 연결된 노드 간의 관계를 표현할 수 있는 자료구조라고 볼 수 있다

그래프 탐색

그래프 탐색은 하나의 정점에서 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다

DFS의 탐색과정

DFS는 그래프 탐색을 하는 알고리즘으로써 가장 상위 노드에서 부터 시작해 가장 하위 노드가 있는 방향을 우선순위로 탐색을 진행한다. 이때 DFS는 스택 자료구조(stack)를 통해 구현한다

트리의 가장 윗부분인 루트 노드를 기준으로 탐색을 시작한다.

루트 노드와 연결된 노드 중에서 방문하지 않은 노드가 있는지 확인을 한다.

방문하지 않은 노드는 스택에 넣는다

(동일한 깊이의 인접한 노드가 여러개가 있다면 이 중 노드의 번호가 작은 것 부터 차례대로 탐색하는 것이 관행이다)

더 이상 방문하지 않은 노드가 없으면 탐색이 완료되었다고 판단하고 스택에서 현재 노드를 제외한다

계속해서 현재 노드에서 하위 노드에 방문하지 않은 노드가 있는지 없는지 확인하고 없으면 상위 노드로 다시 이동하고 있으면 하위 노드로 이동 후 현재 노드를 스택에서 제외한다

위와 같은 과정을 계속해서 반복하고 가장 바깥쪽 노드의 하위 노드까지 탐색을 진행한다

방문하지 않은 노드가 더 이상 존지해지 않으면 해당 노드를 스택에서 제거하고 탐색을 종료한다

[DFS 구현하기]

# DFS - 깊이 우선 탐색 -> 스택을 이용
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
# 방문노드
visited = [False] * len(graph)

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 0번 노드가 없으니 1번 노드부터 탐색
dfs(graph, 1, visited)

[DFS/BFS 탐색 순서 차이점]

---

[BFS]

DFS와는 반대로 ‘넓이 우선 탐색’을 하는 알고리즘이다 
루트 노드에서 시작해서 정점으로터 가장 인접한 노드를 탐색하는 방법이다 
주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾을 때 자주 사용하는 방법이다

BFS의 탐색과정

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

BFS 장단점

장점

• 노드의 수가 적고 깊이가 얕은 경우 빠르게 탐색할 수 있다
• 단순 검색 속도가 DFS보다 빠르다
• 답이 되는 경로가 여러개인 경우에도 최단 경로임을 보장한다
• 최단 경로가 존재한다고 했을 때 어느 한 경로가 무한히 깊어진다고 해도 최단 경로를 반드시 찾을 수 있다

단점

• 재귀호출의 DFS와는 달리 다음에 탐색할 정점들을 저장해야 하기 때문에 저장공간이 많이 필요하다
• 노드의 수가 늘어나면 탐색해야 하는 노드 또한 많아지기 때문에 비현실적이다

[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

Reference

1. https://velog.io/@sohi_5/algorithmDFS
2. https://velog.io/@mgm-dev/간략-자료구조-정리
3. https://security-nanglam.tistory.com/413
4. https://coding-factory.tistory.com/612
5. https://spacebike.tistory.com/39