목록탐색 (1)

맞왜틀

깊이 우선 탐색(Depth First Search, DFS)

📔 깊이 우선 탐색(DFS) 이란 깊이를 우선으로 하여 탐색을 수행하는 알고리즘 특정 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법! ex) 미로탐색 - 막힐 때 까지 계속 가다가 막다른 길이 나오면 가장 최근의 갈림길로 돌아가 다시 길을 찾는 것! 경로를 찾고 싶을 떄 스택와 그래프로 해결한다. ( 재귀함수를 써도 됨 ) 스택으로 사용시 이웃 중 가장 뒤에 있는 것부터, 재귀 사용시 이웃 중 가장 앞에 있는 것부터 탐색한다. 📔 깊이 우선 탐색(DFS) 구현 def dfs(c): print(c, end=' ') for neighbor in adj[c]: # c의 이웃 중 if visited[neighbor] == 0: # 방문 아직 안한 친구이면 visited[neig..
CS/Algorithm 2020. 9. 28. 20:29
이전 Prev 1 Next 다음