목록BFS (1)

초보 개발자의 기록

알고리즘 개념 - 너비 우선 탐색(BFS)

너비 우선 탐색(BFS, breath-first search)그래프를 완전 탐색하는 방법 중 하나시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘기능특징시간 복잡도(노드 수;V, 에지 수:E)그래프 완전 탐색- FIFO 탐색- Queue 자료구조 이용O(V+E) 너비 우선 탐색은 선입선출 방식으로 탐색하므고 큐를 이용해 구현너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 떄 최단 경로를 보장 너비 우선 탐색의 핵심 이론1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요그래프를 인접 리스..
Study/Coding Test 2025. 8. 18. 22:41
이전 Prev 1 Next 다음