[알고리즘 마스터] 6. BFS (너비 우선 탐색)

안녕하세요. 개발감자 박그냥입니다!🥔

오늘은 알고리즘 중  BFS (너비 우선 탐색)에 대해서 정리해보도록 하겠습니다.

 

1. BFS (너비 우선 탐색)

• 기능 : 그래프 완전 탐색 기법 중 하나이다. 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색
• 특징 : 큐 자료구조(FIFO) 이용된다. 선입선출의 방식. 목표 노드에 도착하는 경로가 여러 개일때 최단 경로를 보장해준다.
• 시간 복잡도 : O(V+E)  ->> V : 노드 수 E: 에지 수

 

2. BFS (너비 우선 탐색)의 원리

인접 리스트를 기준으로 원리를 설명합니다.

한 번 방문한 노드는 다시 방문하지 않아 노드 방문 여부를 체크한 배열이 필요합니다. 이는 깊이 우선 탐색과 같습니다.

아래의 사진에 있는 그래프와 인접 리스트를 기반으로 깊이 우선 탐색의 원리를 설명해보도록 하겠습니다.

1) BFS을 시작할 노드를 정한 후에 사용할 자료 구조(노드 방문 여부 저장) 를 초기화합니다.

저는 노드 1을 기준 노드로 설정하여 큐에 넣었습니다.

 

2) 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노트를 다시 큐에 삽입합니다.

큐에서 빼주면서 탐색 순서에 추가해줍니다. 큐에 들어간 노드는 방문 리스트에 저장해줍니다.

쉽게 생각하면 가장 위에 것 빼고 탐색순서 추가하고 인접 노드 넣고 리스트에 추가하고 를 반복한다고 생각하면 좋을 것 같아요.

처음 노드 1을 꺼내고 탐색 순서에 1을 추가합니다.

1의 인접 노드인 2와 3을 순서대로 넣어줍니다. 넣으면서 방문 리스트에 표시도 해줍니다.

 

1의 인접 노드 2와 3 중에서 가장 오른쪽에 위치한 2을 꺼내고 탐색 순서에 추가해줍니다. 

(이미 2의 인접 노드인 3이 들어와있기 때문에 큐에 요소를 넣는 작업은 해주지 않습니다. 인접 노드가 없는 경우에도 그냥 빼주는 작업만 진행합니다.)

 

2의 인접노드인 3을 꺼내고 탐색 순서에 추가해줍니다. 

3의 인접 노드인 4를 큐에 넣어줍니다. 넣으며 방문 리스트에 표시해 줍니다.

 

3) 큐 자료구조에 값이 없을 때까지 반복합니다.

마지막으로 남은 4를 꺼내고 탐색 순서에 추가해줍니다. 

 

---

DFS 공부를 하고 BFS를 공부하니 이해가 더 쉽게 잘 되는 것 같습니다. 

 

그럼 더 유익한 포스팅으로 돌아올게요. 개발감자였습니다!