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

Saemi Min·2023년 2월 19일

Data Structure & Algorithm

목록 보기

8/17

DFS(Depth First Search)

깊이 우선 탐색 알고리즘

개념

: "수직 방향"으로 원하는 노드를 탐색하는 알고리즘

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

코드

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
스택 또는 재귀함수로 구현

리스트를 활용한 DFS 구현

# 리스트를 활용한 DFS 구현
def dfs(graph, start_node):

    # 기본은 항상 두개의 리스트를 별도로 관리해주는 것
    need_visited, visited = list(), list()

    # 시작 노드를 시정하기
    need_visited.append(start_node)

    # 만약 아직도 방문이 필요한 노드가 있다면,
    while need_visited:

        # 그 중에서 가장 마지막 데이터를 추출 (스택 구조의 활용)
        node=need_visited.pop() ##list에서 pop을 활용하면 성능면에서 떨어짐.
        # 만약 그 노드가 방문한 목록에 없다면
        if node not in visited:
            # 방문한 목록에 추가하기
            visited.append(node)

            #그 노드에 연결된 노드를
            need_visited.extend(graph[node])

    return visited

print(dfs(graph, 'A'))

deque를 활용한 DFS 구현

def dfs2(graph, start_node):
    # deque 패키지 불러오기
    from collections import deque
    visited=[]
    need_visited=deque() #성능면에서 list() 형태보다 deque형태가 훨씬 좋다!

    # 시작 노드 설정해주기
    need_visited.append(start_node)

    # 방문이 필요한 리스트가 아직 존재한다면
    while need_visited:
        # 시작 노드를 지정하고
        node=need_visited.pop()

        # 만약 방문한 리스트에 없다면
        if node not in visited:

            # 방문 리스트에 노드를 추가
            visited.append(node)
            # 인접 노드들을 방문 예정 리스트에 추가
            need_visited.extend(graph[node])

    return visited

print(dfs2(graph, 'A'))

재귀 함수를 통한 DFS 구현

def dfs_recursive(graph, start, visited=[]):
    # 데이터를 추가하는 명령어 / 재귀가 이루어짐
    visited.append(start)

    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    return visited
    
print(dfs_recursive(graph, 'A'))

BFS(Breadth First Search)

너비 우선 탐색 알고리즘

개념

: "수평 방향"으로 원하는 노드를 탐색하는 알고리즘

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.

코드

현재 정점에 연결된 가까운 점들부터 탐색
큐를 이용해서 구현

리스트를 활용한 BFS 구현

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']


def bfs(graph, start_node):
    need_visited, visited=[], []
    need_visited.append(start_node)

    while need_visited:
        node = need_visited[0]
        del need_visited[0]

        if node not in visited:
            visited.append(node)
            print(graph[node])
            need_visited.extend(graph[node])
    return visited

print(bfs(graph, 'A'))

예시

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우
=> 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
=> 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

DFS/ BFS 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.
DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

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