DFS, BFS
자료의 검색, 트리나 그래프를 탐색하는 방법, 한노드를 시작으로 인접한 다른노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색하는 것.
정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 방법이 있는 반면에, 모든 경우의 수를 전부 탐색해야 하는경우도 있다. 대표적으로 알파고를 들 수 있습니다. 대국에서 발생하는 모든 수를 계산하고 예측해서 최적의 수를 계산해내기 위해 모든 수를 전부 탐색해야합니다. 이경우 DFS, BFS를 써서 탐색을 하는 것입니다.
DFS(깊이 우선 탐색)
DFS는 끝까지 파고드는 방식으로 그래프 최대 깊이 만큼의 공간을 요구합니다.
그래서 공간을 그만큼 적게 쓰는 장점이 있지만 최단경로 탐색은 어렵습니다.
DFS의 경우 재귀 함수로 구현하는 방법과 스택으로 구현하는 방법 2가지가 있는데 먼저 재귀 함수의 경우는 깊이만큼 최대한 탐색하고 난 후 더이상 갈 수 없게되면 되돌아가서 다른방향으로 다시 탐색해가는 구조입니다.
알고리즘:
1. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문한다.
2. 또 그 노드를 방문해서 깊이 우선으로 인접한 노드를 방문한다.
3. 끝에 도달했을 경우 리턴한다.
DFS(node) = node + DFS(node와 인접하지만 방문하지 않은 다른 노드)
를 계속 방문해나가면 됩니다.
visited = []
def dfs_recursion(adjacent_graph, cur_node, visited_array):
visited_array.append(cur_node)
for adjacent_node in adjacent_graph[cur_node]:
if adjacent_node not in visited_array:
dfs_recursion(adjacent_graph, adjacent_node, visited_array)재귀를 이용한 코드입니다.
1. 시작노드를 방문합니다.
2. 현재 방문한 노드(adjacent_node)를 visted_array에 추가합니다.
3. 현재 방문한 노드(adjacent_node)와 인접한 노드(adjacent_graph[cur_node])중 방문하지 않은 노드에 방문합니다.
그리고 방문하지 않은걸 visited_array를 통해 확인합니다.
다음 스택을 이용한 DFS 알고리즘입니다.
알고리즘
1. 루트 노드를 스택에 넣습니다.
2. 현재 스택의 노드를 빼서 visited에 추가합니다.
3. 현재 방문한 노드의 인접한 노드중 방문하지 않은 노드를 스택에 추가합니다.
4. 2~3반복
5. 스택이 비면 탐색종료
def dfs_stack(adjacent_graph, start_node):
stack = [start_node]
visited = []
while stack:
current_node = stack.pop()
visited.append(current_node)
for adjacent_node in adjacent_graph[current_node]:
if adjacent_node not in visited:
stack.append(adjacent_node)
return visited스택을 이용한 DFS 코드
1. 시작노드를 스택에 넣습니다.
2. 현재 스택의 노드를 빼서 visited에 추가합니다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가합니다.
위 과정을 스택이 빌때 까지 반복하는 코드입니다.
BFS(너비 우선 탐색)
BFS는 최단경로를 쉽게 찾을 수 있습니다. 모든 분기되는 수를 다 탐색하고 올수 있기 때문입니다. 그 대신에 공간을 그만큼 쓰게되기 때무에 시간이 좀 오래걸릴 수도 있습니다.
BFS는 큐로 구현을 하는 방법이 있습니다.
알고리즘
1. 루트노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited에 추가합니다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가합니다.
4. 2부터 반복을 합니다.
5. 큐가 비면 탐새을 종료합니다.
def bfs_queue(adj_graph, start_node):
queue = [start_node]
visited = []
while queue:
current_node = queue.pop(0)
visited.append(current_node)
for adj_node in adj_graph[current_node]:
if adj_node not in visited:
queue.append(adj_node)
return visited큐를 이용한 BFS 코드
1. 시작 노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited에 추가합니다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가합니다.
위 과정을 큐가 빌때까지 반복
