[개념정리] BFS (너비우선탐색)

[YubinShin]

BFS

Breadth First Search
그래프를 완전 탐색하는 방법 중 하나로, 시작노드에서 출발해 시작노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘입니다.
FIFO 탐색
Queue 자료 구조를 사용합니다.
목표 노드에 도착하는 경로가 여러 개 일때 최단 경로를 보장합니다.

기본적으로 완전 탐색 알고리즘입니다. 이는 그래프의 모든 노드를 시스템적으로 탐색한다는 의미입니다. 하지만 특정 목적을 위해 사용될 때, 예를 들어 최단 경로를 찾는 경우, 탐색을 일찍 중단할 수 있는 조건을 설정합니다.

시간복잡도

O(V + E)

원리

구현

준비물

• 노드 방문 여부를 체크할 배열 (스택에 넣으면서 true 로 바꿔줍니다.)
• 그래프를 표현할 인접 리스트
• 선입선출(FIFO)이라서 큐를 사용합니다

방법

1. 탐색를 시작할 노드를 정하고, 사용할 자료구조를 초기화 합니다.

• 방문 여부 체크하는 배열만들기 (visit_array)
• 그래프를 인접 리스트로 변환해두기
• 시작 노드를 큐에 삽입하면서 true 로 바꿔줍니다.

2. 스택에서 노드를 꺼낸 뒤 꺼낸 노드의 인접 노드를 다시 큐에 삽입합니다.

• 큐에서 poll으로 노드 꺼내기
• 인접 노드 큐에 삽입: 꺼낸 노드에 인접한 노드 중 아직 방문하지 않은 노드들을 큐에 추가합니다. (방문 배열에 false라고 되어있는 친구들만)

3. 큐 자료구조에 값이 없을 때까지 반복합니다.
   큐에 노드가 없을 때 까지 이 과정을 반복합니다. 이미 방문한 노드는 큐에 다시 추가하지 않아야 합니다.

한줄 정리

큐에 노드를 삽입할 때 방문 배열을 체크하고, 큐에서 노드를 뺄 때 탐색 순서에 기록하여 인접 노드를 방문 배열과 대조하여 살펴 봅니다.