[알고리즘] DFS와 BFS(개념, 특징, 동작 원리, 파이썬 예시)

DFS(깊이 우선 탐색)

 

DFS(깊이 우선 탐색)는 그래프의 모든 정점을 방문하는 데 사용되는 알고리즘 중 하나입니다. 이 방법은 가능한 한 깊게 그래프를 탐색하며, 더 이상 진행할 수 없는 지점에 도달하면 이전 분기점으로 되돌아가 다른 경로를 탐색합니다. DFS는 스택 또는 재귀함수를 이용할 수 있으며, 그래프의 구조를 이해하거나 복잡한 문제를 단순화하는 데 유용합니다.

 

동작 원리

1. 탐색 시작점 선택: DFS는 그래프의 한 정점에서 시작합니다. 시작점은 그래프의 구조나 문제의 요구에 따라 달라질 수 있습니다.
2. 인접 정점 탐색: 현재 정점에서 방문하지 않은 인접 정점을 선택합니다. 인접 정점 중에서 선택하는 기준은 그래프의 표현 방식(ex: 인접 리스트, 인접 행렬)에 따라 다를 수 있습니다.
3. 깊이 우선 탐색 진행: 선택한 인접 정점을 현재 정점으로 하여 2단계로 돌아가 반복합니다. 이때, 더 이상 탐색할 인접 정점이 없으면 이전 정점으로 돌아갑니다.
4. 백트래킹: 더 이상 탐색할 수 있는 경로가 없을 때, 탐색을 시작한 경로를 되짚어가며 다른 경로를 탐색합니다. 이 과정을 백트래킹이라고 합니다.
5. 모든 정점 방문: 위의 과정을 모든 정점을 방문할 때까지 반복합니다. 이미 방문한 정점은 다시 방문하지 않습니다.

 

특징

• 깊이 우선 탐색 방식: DFS는 가능한 한 깊이 있는 정점을 먼저 방문합니다. 이는 탐색을 시작한 정점에서부터 가장 깊은 부분까지 도달한 후에야 다른 경로를 탐색하는 방식으로 진행됩니다.
• 스택 또는 재귀를 이용한 구현: DFS는 스택을 사용하거나 재귀 호출을 통해 구현할 수 있습니다. 재귀 호출을 사용하는 방식이 더 직관적일 수 있지만, 스택을 사용한 구현 방식은 재귀 깊이 제한에 영향을 받지 않습니다.
• 사이클 감지: DFS는 그래프 내의 사이클을 감지하는 데 사용될 수 있습니다. 방문 중인 정점으로 다시 돌아오게 되면, 그래프 내에 사이클이 존재한다고 판단할 수 있습니다.
• 경로 탐색 및 연결성 검사: DFS는 경로가 존재하는지 여부를 확인하거나, 두 정점이 연결되어 있는지를 검사하는 데 유용합니다. 또한, 모든 경로를 탐색하거나 특정 조건을 만족하는 경로를 찾는 데 사용될 수 있습니다.
• 시간 복잡도: DFS의 시간 복잡도는 그래프의 표현 방식에 따라 다를 수 있습니다. 인접 리스트로 표현된 경우, O(V+E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 인접 행렬로 표현된 경우, O(V^2)입니다.
• 공간 복잡도: 재귀 호출을 사용하는 경우, 호출 스택의 최대 깊이는 그래프의 최대 깊이와 동일할 수 있어, 공간 복잡도는 O(V)입니다.
• 백트래킹과의 관계: DFS는 백트래킹 기법의 기초가 됩니다. 백트래킹은 문제를 해를 찾기 위해 후보 해를 구성해 나가다가, 현재의 후보 해가 목표를 달성할 수 없다고 판단되면 즉시 후보 해를 버리고 다른 후보 해를 탐색하는 방법입니다.

파이썬에서의 DFS 구현

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = set() #방문한 정점을 저장

def dfs(visited, graph, node):
	if node not in visited:
    	print(node)
        visited.add(node)
        for neighbour in graph[node]:
        	dfs(visited, graph, neighbour)
            
dfs(visited, graph, 'A')

 

 

BFS(넓이 우선 탐색)

 

BFS(Breadth-First Search)는 그래프의 모든 정점을 방문하기 위한 알고리즘 중 하나로, 깊이 우선 탐색(DFS)과 대비되는 개념입니다. BFS는 가장 가까운 노드부터 차례대로 탐색해 나가며, 레벨 순서대로 그래프의 모든 정점을 방문하는 방식입니다. 이 알고리즘은 주로 최단 경로를 찾거나 그래프의 연결성을 검사하는 데 사용됩니다.

 

동작 원리

1. 시작 정점 선택: 탐색을 시작할 정점을 선택합니다.
2. 큐 사용: BFS는 탐색 순서를 관리하기 위해 큐(Queue) 자료구조를 사용합니다. 초기에는 시작 정점만이 큐에 들어갑니다.
3. 정점 방문 및 인접 정점 탐색: 큐에서 정점을 하나 꺼내어 방문 처리하고, 해당 정점에 인접한 모든 정점을 순회하며 아직 방문하지 않은 정점을 큐에 추가합니다.
4. 반복 실행: 큐가 빌 때까지 3번 과정을 반복합니다. 이 과정을 통해 그래프의 모든 정점을 방문할 수 있습니다.
5. 레벨별 탐색: BFS는 시작 정점으로부터 각 정점까지의 최단 경로나 거리를 찾는 데 유용합니다. 이는 BFS가 그래프를 레벨별로 탐색하기 때문입니다.

 

특징

• 레벨 별 탐색: BFS는 시작 정점에서 가장 가까운 정점부터 차례대로 탐색하며, 각 정점을 그 거리(레벨)에 따라 방문합니다. 이는 모든 정점을 최단 경로 순으로 방문한다는 것을 의미합니다.
• 큐(Queue) 사용: BFS 구현 시에는 FIFO원칙을 가진 큐를 사용하여 탐색할 정점들을 관리합니다. 시작 정점을 큐에 넣고, 큐에서 정점을 하나씩 꺼내 인접 정점을 모두 큐에 넣는 과정을 반복합니다.
• 최단 경로 및 최소 비용: BFS는 가중치가 없는 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로 또는 최소 비용을 찾는 데 효과적입니다.
• 연결성 검사: 그래프가 연결되어 있는지, 혹은 여러 개의 분리된 부분으로 구성되어 있는지를 판별할 때 BFS를 사용할 수 있습니다.
• 시간 복잡도: BFS의 시간 복잡도는 그래프가 인접 리스트로 표현되었을 때 O(V+E)이고, 인접 행렬로 표현되었을 때 O(V^2)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다.
• 공간 복잡도: 큐에 모든 정점이 저장될 수 있기 때문에 최악의 경우 BFS의 공간 복잡도는 O(V)입니다.
• 활용 분야: BFS는 네트워크 라우팅 알고리즘, 소셜 네트워킹, 사이트에서의 최단 경로 찾기, 퍼즐 게임에서의 해결책 찾기, 그리고 데이터 마이닝 등 다양한 분야에서 활용됩니다.

파이썬에서의 BFS 구현

from collections improt deque

def numIslands(grid):
	number_of_islands = 0
    
    row = len(grid)
    col = len(grid[0])
    visited = [[False]*col for _ in range(row)]
    
    #상하좌우 이동
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    for i in range(row):
    	for j in range(col):
        	if(grid[i][j] == '1' and not visited[i][j]):
            	bfs(i, j) #BFS 실행
                number_of_islands += 1
    
    return number_of_islands


def bfs(x, y):
	visited[x][y] = True
    queue = deque()
    queue.add((x, y))
    while(queue):
    	cur_x, cur_y = queue.popleft()
        for i in range(4):
        	nx = cur_x + dx[i]
            ny = cur_y + dy[i]
            if(nx >= 0 and nx < row and ny >= 0 and ny < col):
            	if(grid[nx][ny] == '1' and not visited[nx][ny]):
                	queue.add((nx, ny))
                    visited[nx][ny] = True

 

 

오늘은 DFS와 BFS에 대해서 알아보았습니다.

알고리즘 관련 자료구조로 Stack과 Queue도 함께 공부해보세요!

2024.04.30 - [IT] - [자료구조] Stack과 Queue? (특징, 사용 사례, 예시)

[자료구조] Stack과 Queue? (특징, 사용 사례, 예시)