너비우선탐색1 [Algorithm] 깊이우선탐색(DFS) 과 너비우선탐색(BFS) DFS 와 BFS 는 각각 Depth-First Search 와 Breadth-First Search 로, 깊이우선탐색과 너비우선탐색을 뜻한다. 둘의 차이점과 코드 구현 방법을 구체적으로 알아보고자 한다. BFS 그래프 자료구조형에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 큐를 이용하여 구현할 수 있다. 구현 단계 큐에 탐색 시작 노드를 삽입한다. 큐의 front 를 방문할 때마다 방문 표시를 하고, popleft() 를 한다. 현재 방문하고 있는 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 큐에 넣는다 현재 방문하고 있는 노드에 방문하지 않은 인접 노드가 없다면 큐의 front 을 꺼낸다 반복 실행하여 큐가 완전히 빌 때 종료한다 from collections import deq.. 2021. 6. 30. 이전 1 다음
