목록bfs 파이썬 (1)

sooleeandtomas

[day25] BFS 기초 (1)

😎 BFS (Breadth-First Search) BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 여기서 가장 가까운 노드란 해당 노드와 같은 레벨에 있는 노드들(형제 노드)을 먼저 순회하는 방식이다. BFS는 "큐" 자료구조를 이용한다. 큐는 FIFO의 질서를 가지는 자료구조이다. 😎 BFS 구현 필수 요소 3가지 1. start Node 루트노드같은 시작 노드가 필요하다. 2. visited Nodes 탐색을 중복하지 않도록 visited노드이면 패스한다. 이를 위해 해당 노드가 visited인지 기억을 해놓는다. 3. queue popLeft가 필요하기 때문에 python에서는 deque를 활용한다. from collections import ..
코딩테스트 알고리즘/탐색 2022. 11. 1. 00:28
이전 Prev 1 Next 다음