[알고리즘] 너비 우선 탐색 : BFS(Breadth-First-Search)

📌  너비 우선 탐색이란?

1. 그래프 탐색 기법
   • 그래프 완전 탐색 기법 중 하나
   • 그래프의 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
   • Queue(큐) 자료구조를 사용해 탐색하며, 탐색 순서는 선입선출(FIFO) 방식을 따른다.
   • BFS는 최단 경로를 보장하기 때문에, 최단 거리 계산이 필요한 문제에서 매우 유용하다.
2. 구현 방식
   • 큐(Queue)를 이용한 구현
     • 시작 노드를 큐에 넣고 방문 표시
     • 큐에서 노드를 꺼낸 뒤, 해당 노드에 연결된 인접 노드들을 큐에 추가하고 방문 여부를 기록
     • 큐가 빌 때까지 이 과정을 반복
   • 방문 여부 확인
     • 방문한 노드를 다시 탐색하지 않도록 방문 여부를 기록하는 것이 중요
     • 이를 통해 중복 탐색을 방지하고, 무한 루프를 방지할 수 있음
3. 탐색 순서
   • BFS는 가까운 노드부터 탐색한다.
   • 모든 인접 노드를 탐색한 뒤 다음 깊이의 노드로 이동

---

🔍 BFS의 주요 특징

1. 레벨 탐색
   • BFS는 레벨별 탐색을 자연스럽게 수행함
   • 각 노드가 탐색된 순서대로 레벨을 구분할 수 있어, 트리 탐색, 최단 거리 문제에 적합함
2. 큐의 효율성
   • BFS는 큐 자료구조를 사용하므로 탐색 순서를 관리하기 쉬움
   • 큐에 삽입 및 제거 작업은 O(1)이므로 BFS의 시간 복잡도는 그래프의 노드와 간선 수에 비례함
3. 그래프의 모든 노드 탐색
   • BFS는 그래프의 모든 노드를 탐색하므로, 연결된 구성 요소를 확인하거나 모든 경로를 탐색해야 하는 문제에 적합함
   • 그러나 간선의 수가 많은 경우 메모리 사용량이 증가할 수 있음
4. 시간 복잡도
   • BFS의 시간 복잡도는 O(V + E)입니다.
   • V는 노드 수, E는 간선 수를 나타냄
     ➡️모든 노드와 간선을 한 번씩 방문하기 때문

---

🔧 BFS의 활용과 문제 유형

1. 최단 경로 찾기
   • BFS는 모든 간선의 가중치가 동일한 그래프에서 최단 경로를 보장함
2. 그래프의 연결 요소 탐색
   
   • BFS를 이용해 그래프의 모든 연결 요소를 탐색하고 그룹화함
3. 위상 정렬
   
   • 방향성 있는 비순환 그래프(DAG)에서 BFS를 활용해 위상 정렬을 수행함
4. 레벨 탐색
   
   • BFS는 노드들을 "레벨 순서"로 탐색하기 때문에 트리 또는 그래프의 계층적 구조를 확인할 때 유용함

 

---

🚫BFS 사용 시 주의할 점

1. 메모리 사용량 증가
   • BFS는 큐(Queue)를 사용해 탐색 노드를 저장하므로, 탐색할 노드가 많을수록 메모리 사용량이 급격히 증가할 수 있음
     ➡️ 그래프의 크기와 연결 노드의 수를 고려하여 효율적으로 설계하거나,  노드 방문 여부를 빠르게 확인할 수 있는 배열이나 집합(set) 사용.
2. 최단 경로 제한 조건
   • BFS는 모든 간선의 가중치가 동일한 경우에만 최단 경로를 보장함.
     ➡️ 가중치가 다양한 경우, 다익스트라 알고리즘 등 다른 탐색 방법을 사용해야 함
3. 큐(Queue) 오버플로
   • BFS의 큐에 탐색 대기 중인 노드가 너무 많아지면 메모리 부족이나 프로그램 비정상 종료가 발생할 수 있음. 특히 격자형 그래프나 완전 그래프에서는 탐색 폭이 급격히 증가할 가능성이 큼
     탐색 범위를 제한하거나 노드의 방문 여부를 꼼꼼히 관리하여 큐 크기를 최적화.
4. 무한 루프 방지
   • 방문 노드를 기록하지 않으면 중복 탐색으로 무한 루프에 빠질 수 있음
     ➡️ 방문 여부를 기록하는 배열이나 자료구조를 사용하여 이미 방문한 노드를 재탐색하지 않도록 관리.

---

🚀 DFS와 BFS 비교

특징	DFS	BFS
탐색 방식	한 분기를 최대 깊이까지 탐색 후 복귀	가까운 노드부터 탐색
구현 복잡도	간단함(재귀/Stack 활용)	상대적으로 복잡함(Queue 활용)
속도	느릴 수 있음	단순 검색 속도는 더 빠름
메모리 사용량	적음	상대적으로 많음
적합한 경우	모든 경로를 확인해야 하는 경우	최단 경로를 탐색해야 하는 경우

---

🥐 너비 우선 탐색 과정

1️⃣ BFS 준비 단계

1. 시작 노드 선택
   • 탐색을 시작할 노드를 선택함
2. 자료구조 초기화
   • 인접 리스트 또는 인접 행렬로 그래프를 표현하여 탐색 경로를 관리함
   • 방문 배열을 초기화하여 각 노드의 방문 여부를 기록함
   • 시작 노드를 큐(Queue)에 삽입하고 방문 배열에서 해당 노드를 True로 설정함

2️⃣ 탐색 과정 (반복)

1. 큐에서 노드 꺼내기
   • 큐에서 노드를 꺼내 탐색 순서에 기록합니다.
2. 인접 노드 탐색
   • 꺼낸 노드의 인접 리스트를 확인하여 연결된 노드를 처리
   • 방문하지 않은 인접 노드만 큐에 삽입하고 방문 배열을 업데이트
   • 중요❗️ 이미 방문한 노드는 재삽입하지 않아야 함

3️⃣ 종료 조건

• 큐가 빌 때까지 위 과정을 반복
• 모든 노드가 탐색되면 종료하며, 방문 배열에 따라 탐색된 순서를 확인할 수 있음

✨ 차이점

• DFS: 스택(재귀)을 사용하며 깊이를 우선 탐색.
• BFS: 큐를 사용하며 너비를 우선 탐색.

---

💡 DFS 동작 방식 예제

 

1️⃣ BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

• BFS도 DFS와 마찬가지로 방문했던 노드는 다시방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요함
• 그래프를 인접리스트로 표현하는 것 역시 DFS와 동일함
• DFS와 차이점은 탐색을 위해 스택이 아닌 큐를 사용하는 것

큐 초기 상태

• 시작 노드 1 삽입: 큐 [1]
• 방문 배열: T, F, F, F, F, F

2️⃣ 큐에서 노드를 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

• 큐에서 노드를 꺼내면서 인접노드를 큐에 삽입함
• 이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않음
• 또한 큐에서 꺼낸 노드는 탐색 순서에 기록함

스택에서 1 꺼내기

• 1의 인접 노드 2, 3 중 3부터 삽입: 스택 [3, 2]
• 방문 배열: T, T, T, F, F, F

3️⃣ 큐 자료구조에 값이 없을 때까지 반복하기

• 큐에 노드가 없을 때까지 앞선 과정을 반복함
• 선입선출 방식으로 탐색하므로 탐색 순서가 DFS와 다름

🚨이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심 ❗️

• 큐에서 2 꺼내기
  • 2의 인접 노드 5, 6을 삽입: 큐 [3, 5, 6]
  • 방문 배열: T, T, T, F, T, T
• 큐에서 3 꺼내기
  • 3의 인접 노드 4 삽입: 큐 [5, 6, 4]
  • 방문 배열: T, T, T, T, T, T
• 큐에서 5 꺼내기
  
  • 5에 인접 노드가 없으므로 종료
• 큐에서 6 꺼내기
  
  • 6에 인접 노드가 없으므로 종료
• 큐에서 4 꺼내기
  • 4의 인접 노드 6은 이미 방문했으므로 삽입하지 않음.

➡️ 최종 탐색 순서: 1 → 2 → 3 → 5 → 6 → 4

 

---

✅ 핵심 포인트

 

• 큐 사용: BFS는 큐(Queue)를 사용하여 노드를 탐색하며, 큐의 선입선출(FIFO) 특성에 따라 가까운 노드부터 차례대로 탐색
• 최단 경로 탐색: BFS는 모든 간선의 가중치가 동일할 경우 최단 경로를 보장하며, 최초로 방문한 노드를 통해 가장 빠른 경로를 찾음
• 방문 배열 활용: 각 노드의 방문 여부를 기록하여 중복 탐색을 방지하고, 이미 방문한 노드는 다시 큐에 삽입하지 않도록 함

 

 

 

✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!

[JAVA][Baekjoon] 1260번 DFS와 BFS

[JAVA][Baekjoon] 2178번 미로 탐색