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

Use

* 최단경로 찾기에 적합

* 미로찾기, 자율주행 최단거리 등에 사용됨

Big O

* O(N^2)

How?

* Queue 이용

1. 큐 초기화

2. 시작위치를 queue의 현재 위치에 저장

3. 해당 위치에서 인접한 곳 갈수 있는지 검사

갈수 있으면 거리 증가시키고,

방문했으니 방문좌표 변경해줌

갈수있음을 확인한 그 좌표의 위치를 queue에 저장

2번, 3번 반복

최종적으로 좌표가 도착지와 같아지면

그때의 거리 출력이 최단거리

비슷한 DFS 는 재귀함수를 이용하여 구현한다.

Detail

구성요소

1. vertex (edge) :

2. 인접행렬 : 어느 vertex 들이 어느 변으로 연결되는지 나타내는 정사각형 행렬

3. 방문여부 플래그

시나리오

1. start vertex : 0

2. Queue에 vertex 0 을 넣음.

3. 큐에서 요소를 빼는데, 이때 요소는 현재 vertex.

이 현재 vertex를 반복문으로 돌면서 위치를 바꿔가며 queue에 넣는다.

4. 현재 vertex에서 인접한 요소들을 queue에 넣는다.(enqueue)

이 요소는, 당연히 방문한적이 없는 요소여야 함.

5. 더이상 현재 vertex에 인접한 요소가 없으면, queue에서 요소하나를 뺀다.(dequeue)

다음 vertex. 3~5를 반복한다.

참고 사이트

Luck is the residue of design