th42500의 TIL

BFS (Breadth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ BFS 그래프에서 부모 노드를 먼저 방문한 후, 방문했던 부모 노드의 자식 노드를 차례로 탐색하는 알고리즘으로, 너비 우선 탐색이라고도 불림 선입선출 형태의 Queue자료구조 활용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도 : O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 Queue에 삽입하고 방문 처리 2️⃣ Queue에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 3️⃣ 2️⃣ 과정을 수행할 수 없을 때까지 반복 ✔ 예시 1️⃣ 시작 ..