BFS (Breadth First Search)

BFS
Breadth First Search
너비우선 탐색
가까운 정점을 먼저 방문, 먼 정점은 나중에 방문
Queue로 구현
코딩테스트에서 중요하다.
횟수가 정해져있는 한에서 찾을 수 있으면 BFS를 사용한다.
문제 유형: 임의의 지점에서 다른 지점을 가는 문제
상태 트리, level 트리
출발(루트) → 도착까지 최단 거리
레벨로 거리 구하기
최단 거리를 구하는 방법론이다.
시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘
출발점을 먼저 Queue에 넣고, Queue가 빌 때까지 아래 과정을 반복한다.
- Queue에 저장된 정점을 하나 Dequeue한다.
- 그리고 뺀 정점과 연결된 모든 정점을 Queue에 넣는다.