[알고리즘] DFS & BFS 알고리즘(3) - BFS 알고리즘

2022.12.24 - [백준 알고리즘] - [알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘

[알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘

DFS 알고리즘에 대한 정리는 위 포스팅에서 확인

 

본 포스팅에서는 BFS 알고리즘에 대한 정리 내용을 담고있습니다.

 

(본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.)

 

 

https://www.youtube.com/@dongbinna

동빈나

 

 

 

 

 

---

 

 

BFS 란?

BFS는 Breadth-First Search의 약자로

너비 우선 탐색이라고 부르며

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

 

이런 BFS는 큐 자료구조를 이용한다.

 

 

 

BFS의 동작과정을 정리하면 다음과 같다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

 

2. 큐에서 노드를 꺼낸 후에 해당 노드의 인접 노드 중에서

방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리

 

3. 더 이상 2번 과정을 수행할 수 없을 때까지 반복!

 

위와 같은 설명을 글로만 읽으면 와닿지 않을 수 있기에

관련 이미지 자료를 가져와봤다. (물론 이것역시 이코테 강의에서....)

 

 

 

위와 같은 그래프가 있다고 상황을 설정해본다. 

 

 

 

 

위에 정리한 동작 순서대로 진행해보면, 

가장 먼저 시작 노드인 '1'을 큐에 삽입하고 방문 처리를 한다. 

 

 

 

 

 

다음으로는 '스택'이 아닌 '큐' 자료구조이기때문에

큐에서 노드 1을 꺼낼 수 있음.

 

큐에서 노드 1을 꺼내고, 방문하지 않은 인접 노드 '2', '3', '8'을 큐에 삽입하고

방문 처리함.

 

 

 

 

 

다음으로는 이전과 같이 동일한 방법으로 큐에서

노드 '2'를 꺼내고, 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문처리한다. 

 

 

 

 

 

 

동일한 방법으로 진행해준다. 

 

 

 

 

 

계속해서 진행하다보면 위의 사진과 같이

'8' 노드를 꺼냈는데 방문하지 않은 인접노드가 없는 경우가 생길 수 있다. 

(이런경우는 그냥 무시하면됨)

 

 

결국 이 과정을 계속해서 반복하여 전체 노드의 탐색순서

즉, 큐에 들어간 순서는 아래와 같다. 

 

1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6