목록Depth First Search (1)

Data Scientist(DS)

S533 BFS, DFS

BFS (Breadth First Search) : 너비 우선 탐색 개념 최대한 넓게 탐색하는 것 큐의 개념이 사용된다. 위 이미지를 참조하자면, s - 1 - 2 - 3 - 4 - 5 - 6 - 7 순서로 탐색한다. 활용 최단거리를 구하는 문제 ex) 미로찾기 등 장/단점 장점 무한히 깊은 경로여도 최단 경로를 반드시 찾을 수 있고 최단 경로 찾기에 적합하다. 노드 수가 적고 깊이가 얕을 때 효과적으로 찾을 수 있다. 단점 큐를 이용하기 때문에 노드 수가 많아지면 메모리를 많이 소비한다. 노드 수가 많아지면 탐색할 노드가 많아져 비효율적이다. 코드 구현 # 첫번쨰 방법 def bfs_queue(start_node, bfs_graph): bfs_list = list() queue = list() queu..
AI 부트캠프/Computer Science 2021. 12. 6. 21:29
이전 Prev 1 Next 다음