DFS VS BFS

오성민·2022년 10월 24일

CS 코딩테스트

CS

목록 보기

2/10

코딩 테스트라는 키워드로 찾아본다면 분명히 듣는 유형 중에는 DFS,BFS가 꼭 있다. 그렇게 계속해서 나오는 것은 분명 중요하다는 것이기에 공부하면서 까먹지 않기 위해 글을 작성한다.

DFS , BFS

DFS(깊이 우선 탐색) 와 BFS(넓이 우선 탐색) 은 그래프 탐색 알고리즘이다.

'그래프'라는 자료구조에 대해서 자세히 내용을 작성하기에는 너무 길어질 것 같기 때문에 간단히 작성을 한다.
그래프는 연결된 원소 간의 관계를 표현한 자료구조이다.
그래프는 객체를 나타내는 노드와 객체를 연결하는 간선의 집합으로 구성된다.

그래프 탐색 알고리즘은 특정한 알고리즘을 사용해서 그래프에 존재하는 노드를 방문하는 알고리즘이다.
이름에서도 알 수 있듯이 DFS와 BFS의 차이점은 노드를 방문하는 순서이다.

DFS

DFS는 깊이 우선 탐색이라는 뜻이다. 이러한 이름에서도 알 수 있듯이 그래프를 탐색할 때에 탐색을 시작하는 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다

모든 노드를 방문하고자 할 때에 선택
보다 좀 더 간단함
속도가 보다 느림

구체적인 동작 과정:

탐색 시작 노드를 스택에 삽입하고 방문 처리. (이미 방문(탐색)했던 노드를 재방문하지 않기 위해)
스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문 처리. 만약 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄.
2번의 과정을 더 이상 수행할 수 없을 때까지 반복.

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

# 방문 정보를 기록하기 위한 리스트
visited = [False] * 8

def dfs(v):
    # 방문 표시
    visited[v] = True
    print(v, end=' ')
    # 그래프를 순환하면서 인접 노드들을 방문
    for i in graph[v]:
        # 만약 방문하지 않은 노드가 있다면
        if not visited[i]:
            # 탐색 시작
            dfs(i)

# 탐색 시작 노드 1을 넣어주며 dfs() 실행
dfs(1)

BFS

BFS 너비 우선 탐색이라는 이름에 걸맞게 시작 노드에서 인접한 노드를 먼저 탐색하는 방법임.
주로 최단 경로를 찾고 싶을 때 이 방법을 선택

구체적인 동작 과정:

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

from collections import deque

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

visited = [False] * 8

def bfs(v):
    # 큐 생성 및 큐에 시작 노드 삽입
    q = deque()
    q.append(v)
    # 아직 방문해야 하는 노드가 있다면
    while q:
        # 큐에서 노드를 꺼내서 x에 저장
        x = q.popleft()
        print(x, end=' ')
        # 그래프를 탐색하다가 방문하지 않은 노드가 있다면
        for i in graph[x]:
            if not visited[i]:
                # 큐에 방문하라고 삽입하고 방문 처리
                q.append(i)
                visited[i] = True

bfs(1)

문제 유형

그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.
경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

응용

이렇게 둘의 차이점을 알아봤는데, 과연 어느 때에 DFS를 사용해야 하며, 어느 때에 BFS를 사용해야 할까? 적절한 사용법을 알기 위해 둘의 장단점을 알아보자.

DFS 장점

현 경로상의 노드들만 기억하기 때문에 적은 메모리를 사용. (공간 복잡도)
목표 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 탐색 가능.

DFS 단점

해가 없는 경로를 탐색할 경우 단계가 끝날 때까지 (현 경로의 가장 끝까지) 탐색함.
- 답이 아닌 경로가 매우 깊다면, 그 경로에 깊이 빠지게 됨.
- 여러 경로 중 무한한 길이를 가지는 경로가 존재하고 해가 다른 경로에 존재하는 경우, 무한한 길이의 경로에서 빠져나오지 못해 영원히 종료하지 못함
- 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 (재귀로 구현한다면 재귀 호출 횟수를 제한하는 등), 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용해야 함.
목표에 이르는 경로가 다수인 경우, DFS는 해에 도착하면 탐색을 종료하기에 얻어진 해가 최단 경로라는 보장이 없음.

BFS 장점

모든 경로를 탐색하기에 여러 해가 있을 경우에도 최단 경로임을 보장함.
최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있음.
- 여러 경로 중 무한한 길이를 가지는 경로가 존재하더라도, 모든 경로를 동시에 탐색을 진행하기 때문에 탐색 가능.
노드의 수가 적고, 깊이가 얕은 해가 존재할 때 유리함.
-탐색하는 트리 또는 그래프의 크기에 비례하는 시간 복잡도를 가짐.