탐색(Search)
에 대해 생각해 볼 필요가 있다.여기까지 보았을 때 탐색 알고리즘에는 각 특징들이 있고 왜? 쓰는지에 대해 대략적으로 해소는 되지만 실제 코딩 문제에 봉착했을 때 DFS를 쓸 지 BFS에 대해서는 판단 기준은 서지 않는다. 일단은 DFS와 BFS에 대해 자세히 알아보자!
반복하다가 → 갈 수가 없게 되면 → 탈출 조건
즉, 재귀함수를 이용해서 구현할 수 있음
재귀함수는 stack 특성을 가짐 즉, stack을 이용해 DFS를 구현한다는 것을 의미
재귀함수는 F(n+1) = ? X F(n) 구조를 찾는 것이 중요! (TIL-1 재귀함수 참고)
DFS(node) = node + DFS(node와 인접하지만 방문하지 않은 다른 node)로 생각해 볼 수 있음
graph = {
1: [2, 5, 9],
2: [1, 3],
3: [2, 4],
4: [3],
5: [1, 6, 8],
6: [5, 7],
7: [6],
8: [5],
9: [1, 10],
10: [9]
}
graph = [[],
[2, 5, 9],
[1, 3],
[2, 4],
[3],
[1, 6, 8],
[5, 7],
[6],
[5],
[1, 10],
[9]]
구현 방법
1. 루트 노드부터 시작한다.
2. 현재 방문한 노드를 visted =[] 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문한다.
4. 2, 3을 반복하며 계층 끝에 도달한다.
왜 stack을 이용하는지에 대한 생각
stack은 FILO인 선입후출 개념
따라서 처음 시작 노드와 인접한 노드를 모두 저장해두고
가장 왼쪽의 노드의 모든 계층을 탐색한 이후
되돌아와 저장해 둔 노드 중 방문하지 않은 다음 노드로 넘어감
→ 이런 논리는 stack으로 구현하면 알맞음
예시를 통한 이해
1과 인접한 (2, 5, 9) 저장
→ 2와 인접한 3
→ 3과 인접한 4
→ 다시 돌아와 1과 인접한 5를 탐색 이후 반복
visited = []
# dictionary의 경우
def dfs_recursion(adjacent_graph, cur_node, visited_array):
visited_array.append(cur_node)
for adjacent_node in adjacent_graph:
if adjacent_node not in visited_array:
dfs_recursion(adjacent_graph, adjacent_node, visited_array)
return
# list의 경우
def dfs_recursion(adjacent_graph, cur_node, visited_array):
visited_array.append(cur_node) # (1)
for adjacent_node in adjacent_graph[cur_node]: # (2)
if adjacent_node not in visited_array: # (2)
dfs_recursion(adjacent_graph,adjacent_node,visited_array) # (3)
return visited_array # (4)
dfs_recursion(graph, 1, visited)
print(visited)
(result)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
위의 예제는 DFS의 가장 뼈대가 되는 것으로 이해가 중요!
graph = [[],
[2, 3, 4],
[1,5],
[1,6, 7],
[1,8],
[2,9],
[3,10],
[3],
[4],
[5],
[6]]
from collections import deque
def bfs_queue(adj_graph, start_node):
queue = deque([start_node]) # (1)
visited = [] # (1)
while queue: # (2)
current_node = queue.popleft() #(3)
visited.append(current_node) #(3)
for adj_node in adj_graph[current_node]:
if adj_node not in visited:# (4)
queue.append(adj_node)
return visited
queue.popleft()
를 이용해 첫번째 인덱스의 원소를 꺼낸 후 visited에 추가한다.확실히, 재귀함수를 이용하는 DFS보다 이해하기는 쉬움!