알고리즘: 너비 우선 탐색 (Breadth First Search)

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

 

• 기준점에서 가장 인접한 후보부터 탐색
• 한 길을 깊이 확인하는 깊이 우선 탐색 (DFS)와 비교됨
• 최단 경로 구하기에 주로 사용됨. 목적지 발견시 바로 종료할 수 있어 DFS에 비해 빠른 경우가 많음
• 재귀로 시스템 스택을 사용하는 DFS에 비해 queue를 사용해 스택오버플로우 (Stack over flow)에서 비교적 자유롭고,
  힙(Heap) 공간을 넓게 사용할 수 있어 넓은 탐색 범위에 유리함 

 

탐색

 

1. 초기 Queue에 시작 좌표를 넣고 다음 과정 반복
2. Dequeue 좌표에서 이동 가능한 모든 경로를 Enqueue 함
3. 다시 Dequeue 좌표에서 이동 가능한 모든 경로를 Enqueue함 
4. 도착 지점에 도달할 때까지 2 ~ 3과정 반복

- 양쪽으로 번갈아가며 탐색해 나가기에 더 빨리 도착하는 곳을 찾을 수 있음.

 

 

탐색 예제

 

--> (위 그림이 마지막은 아님) 디큐시 S에 도달한 것이 확인되면 종료되고, 결과 값은 4 이다.

 

 

Queue

- Dequeue : 큐의 앞 원소를 삭제하며 리턴
- Enqueue : 큐에 원소 삽입

 

 

예제: 미로 최단거리 찾기

 

강의

 

 

 

자바 코드

 

Jeong-sky-1003/DataStructure

 

 

동작 콘솔 출력

 

 

- 이하 출력물은 생략하나, 위 그림처럼 물결이 퍼져나가듯이 탐색하는 과정을 볼 수 있음