미로찾기 알고리즘

그래프 탐색 알고리즘에는 대표적으로 깊이 우선 탐색과 너비우선 탐색이 있습니다.

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)
• 비교

1. DFS

깊이 우선 탐색(Depth First Search)으로 해당 노드의 자식 노드를 먼저 탐색하는 알고리즘입니다.

wikimedia commons

1) 스택 사용

DFS를 스택을 사용하게되면 재귀 없이 구현할 수 있게 됩니다. 방문이 필요한 노드를 스택에 저장하고 스택 구조를 활용하여 그 중 가장 마지막 데이터를 추출합니다.

2) 코드

def dfs(graph, start_node):
    visited = []
    stack = [start_node]

    while stack:
            node = stack.pop()
            if node not in visited:
                    visited.append(node)
                    stack.extend(graph[node])
    return visited

graph = {
    1: [2, 5, 9],
    2: [3],
    3: [4],
    4: [],
    5: [6, 8],
    6: [7],
    7: [],
    8: [],
    9: [10],
    10: []
}

print(dfs(graph, 1))
# output : [1, 9, 10, 5, 8, 6, 7, 2, 3, 4]

코드가 재귀적이기 때문에 재귀함수로도 구현할 수 있습니다.

def dfs_recursive(graph, start, visited = []):
		visited.append(start)
		for n in graph[start]:
				if n not in visited:
						dfs_recursive(graph, n, visited)
		return visited

print(dfs_recursive(graph, 1))
# output : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

2. BFS