yoon's Devlog

dfs는 깊이 우선 탐색으로 자식노드부터 탐색하는 기법이고, bfs는 넓이 우선 탐색으로 형제노드들부터 탐색하는 기법이다. dfs를 구현하는 방법으로는 스택을 사용하는 방법과 재귀를 사용하는 방법이 있고, bfs를 구현하는 방법은 큐 혹은 데크를 사용하는 방법이 있다. dfs를 구현할 때에는 이미 방문한 노드 정보를 저장하는 visit과 앞으로 찾아가야할 노드를 기준으로 데이터를 탐색한다. 이미 방문을 했다면 무시하고, 방문하지 않았다면 탐색한다. 그럼 우선 dfs 구현 방법을 살펴보자. 1. 스택 활용 방법 def dfs(graph, start_node): visit = [] stack = [] stack.append(start_node) while stack: node = stack.pop() if ..