[Algorithm/Python] DFS(Depth First Search) / BFS(Breadth First Search) 구현 정리(1)

대표적인 탐색 알고리즘인 DFS와 BFS는 스택과 큐, 재귀 함수를 이용하여 정리할 수 있다.

 

DFS(Depth First Search)

DFS는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

 

그래프는 다음과 같이 두 방식으로 쓰일 수 있다.

1. 인접 행렬 방식

INF = 999999999 #무한의 비용 선언

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
	[0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

# [[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]

2. 인접 리스트 방식

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))

# 노드2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))

print(graph)

# [[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]

 

 

dfs 문제를 풀 때는 항상 어떤 노드를 앞으로 찾아갈지와 이미 방문한 노드인지를 확인해야 한다.

 

스택, 큐, 재귀함수를 이용하여 dfs를 다음과 같이 구현할 수 있다.

스택/리스트를 활용한 DFS 구현

need_visited = []
visited = []

def dfs(graph, start_node):
    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

 

큐를 활용한 DFS 구현

import sys
from collections import deque

need_visited = deque()
visited = []

def dfs(graph, start):
	need_visited.append(start)

	while need_visited :
		node = need_visited.pop()

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

 

재귀함수를 활용한 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​