(3장-2) BFS(너비우선탐색) 알고리즘이란?

안녕하세요. 지칸입니다.

 

오늘 설명할 알고리즘은 BFS입니다.

삼성 SW역량테스트에서 자주 사용되는 알고리즘 중 하나로 앞에서 공부한 DFS와 비슷한 역할을 합니다.

(주로 2차원 좌표상에서의 문제에 사용)

 

1) BFS란?

2) 구현하기

---

1) BFS란?

이전 편에서 그래프 개념과, DFS에 대해 공부하였습니다.

mydirectorystory.tistory.com/15

(3장-1) DFS(깊이 우선탐색) 알고리즘이란?

BFS란 인접한 정점순으로 탐색하는 알고리즘을 의미합니다.

DFS에서 설명했던 예제를 동일하게 설명해 보겠습니다.

분기점에서는 자신 기준 왼->오 순으로 방문한다는 가정을 했습니다.

1. 시작점 정점0에서 1, 3, 6의 분기점에서 방문 가정에 따라 정점1부터 방문합니다. (0->1)
2. 그다음 정점3을 방문합니다. (0->1->3)
3. 다음 정점6을 방문합니다. (0->1->3->6)
4. 정점0과 연결된 정점이 더 없으니 정점0 다음으로 방문했던 정점1로 이동합니다(1->3->6)
5. 그다음 방문한 정점1에서 부터 연결된 정점2를 방문합니다.(1->3->6->2)
6. 마찬가지로 새로운 연결 정점이 없으니 그다음 정점부터 동일한 과정을 거치면됩니다.
7. 모든 과정을 반복하여 더 이상 새로운 정점이 없다면 종료합니다.

BFS 알고리즘의 동작 순서대로 글로 설명해봤습니다.

여기서 우리는 아래 본문에서 이야기한 Queue구조가 떠오를 것입니다.

mydirectorystory.tistory.com/17

큐 란? (STL 사용법)

현재 정점에서 연결된 모든 정점을 순서대로 Queue에 입력 후 본인은 queue에서 빠지고

현재 정점 다음으로 Queue에 들어온 정점부터 동일한 동작을 수행합니다.

---

2) 구현하기
c++로 queue STL를 사용하여 구현하면 아래 코드와 같습니다.

우리가 원하는 정점 순으로 출력이 되는 걸 확인할 수 있습니다.

DFS알고리즘과 마찬가지로 모든 정점을 검색하는 방식으로 코딩을 했습니다.

DFS와 BFS의 차이점은 매우 단순합니다.

위 그림에서처럼 자료구조를 어떤 걸 썼는지(함수 호출명이 조금 다름)

모든 정점을 찾아서 넣을지, 1개만 찾고 말 건지

언제 pop으로 현재 정점을 내보낼지

 

이렇게 3가지의 포인트만 수정하면 우리는 DFS/BFS를 자유롭게 수정해서 쓸 수 있습니다.

문제 유형마다 어떤 알고리즘을 선택해야 할지 고민해야 하는 순간이 오며

우리는 얼마든지 간단하게 바꿔가며 사용할 수 있습니다.

위 코드의 템플릿을 잊지 마세요!