알고리즘
BFS
다른 이름: Breadth-First Search , 너비 우선 탐색
정의
Breadth-First Search. 너비 우선 탐색. 그래프/트리를 레벨 순으로 방문. 큐 사용. 최단 경로 보장(가중치 없는 그래프). 레벨 순회, 최단 거리, 가장 가까운 노드 찾기에 최적. O(V+E) 시간복잡도
상세 설명
기술 스펙
- 시간복잡도: O(V+E) - 모든 정점(V)과 간선(E) 방문
- 공간복잡도: O(V) - 큐에 최대 V개 저장
- 구현: 큐 (FIFO) 사용
- 방문 순서: 시작 노드 → 레벨 1 → 레벨 2 → ...
- 최단 경로: 가중치 없는 그래프에서 보장
실무 활용
- 최단 경로: 미로 최단 거리, 체스 나이트 최소 이동
- 레벨 순회: 트리 레벨별 출력
- 가장 가까운 노드: 출발점에서 가장 가까운 목표
- 연결 요소: 그래프 연결 여부 확인
- 백준: 2178 (미로 탐색), 7576 (토마토)
장점
- 최단 경로 보장: 가중치 없는 그래프
- 레벨 순회: 거리별 처리 가능
- 안정적: 무한 루프 없음 (방문 체크)
- 직관적: 가까운 곳부터 탐색
단점 및 제약
- 메모리 사용: 큐에 모든 레벨 저장
- 가중치 그래프: Dijkstra 사용 필요
- 모든 경로 탐색 불가: 하나의 경로만
- DFS 대비 느림: 백트래킹 문제
호환성
C++ STL (queue), Python (collections.deque), Java (Queue)
표준 정보
표준화 기구: 알고리즘 교과서 표준. ACM ICPC, 코딩 테스트 필수
출시 연도: 1959년