BFS를 선택해야 하는 코딩테스트 문제 유형 및 사고 흐름

📌 BFS를 선택해야 하는 코딩테스트 문제 유형 및 사고 흐름

코딩테스트 문제를 읽고 BFS를 선택해야 하는 단서를 찾는 방법을 단계별로 정리하겠습니다.

BFS는 최단 거리 탐색, 레벨별 탐색, 연결된 요소 찾기에 적합합니다.

---

Step 1: 최단 거리(Shortest Path) 문제인가?

✅ BFS는 "가중치가 없는 그래프"에서 최단 경로 탐색에 가장 적합

✅ 문제에서 "최단 거리" 또는 "최소 이동 횟수"를 찾으라고 하면 BFS를 고려

•   예시
  •   미로에서 출발점 → 도착점까지 가는 최단 거리 찾기
  •   그래프에서 두 노드 간 최소 이동 횟수 구하기

📌 예제 문제

문제: 0과 1로 이루어진 미로에서 (0,0) → (N-1,M-1)까지 이동하는 최단 거리를 구하시오.

BFS 선택 이유: 한 단계씩 이동하며 방문하는 방식이므로, 최단 경로를 보장.

---

Step 2: 그래프에서 "가까운 노드부터 탐색"해야 하는가?

✅ BFS는 "가까운 곳부터 탐색"하므로, 연결된 요소를 찾는 문제에 유리

✅ 모든 노드를 방문하면서 가장 빠른 경로를 찾아야 하는 경우 BFS 적합

•   예시
  •   그래프에서 특정 노드까지 가장 빠르게 도달하는 방법 찾기
  •   "몇 번 만에 목적지까지 도달하는가?"를 묻는 문제

📌 예제 문제

문제: 1번 노드에서 N번 노드까지 가는 최소 이동 횟수를 구하시오.

BFS 선택 이유: BFS는 너비 우선 탐색이므로, 최소 이동 횟수를 쉽게 찾을 수 있음.

---

Step 3: "단계별 탐색"이 필요한가?

✅ BFS는 "레벨별 탐색(단계별 탐색)"에 적합

✅ 한 번의 탐색에서 한 레벨씩 탐색해야 하는 경우

• 예시
  •   특정 거리(레벨)에 있는 노드 찾기
  •   특정 거리까지 확산되는 문제 (예: 전염병, 파도 확산)

📌 예제 문제

문제: 각 노드에서 "K번 이동했을 때 도달 가능한 노드 개수"를 구하시오.

BFS 선택 이유: BFS는 레벨(단계)별 탐색이 가능하므로, K번 이동한 후 노드 개수를 쉽게 찾을 수 있음.

---

Step 4: 최단 거리와 유사한 "최소 횟수"가 있는가?

✅ "최소한 몇 번의 이동이 필요한가?"라는 질문이 있다면 BFS를 고려

✅ DFS는 깊이 탐색으로 불필요한 경로를 탐색할 가능성이 있음.

• 예시
  •   특정 목표를 달성하는 데 필요한 최소 단계 찾기 (예: 최소 점프 횟수)

📌 예제 문제

문제: 점프해서 도착지에 도달하는 최소 횟수를 구하시오.

BFS 선택 이유: BFS는 한 번에 한 단계씩 탐색하므로, 최소 횟수를 보장.

---

 Step 5: "모든 정점을 탐색"해야 하는가?

✅ BFS는 그래프에서 "연결된 모든 정점"을 탐색하는 데 적합

✅ DFS는 깊이 우선이므로 한 경로를 끝까지 탐색 후 돌아오므로 비효율적

• 예시
  •   네트워크에서 연결된 모든 컴퓨터 찾기
  •   섬의 개수 세기 (2차원 격자 탐색)

📌 예제 문제

문제: N×M 크기의 섬 지도에서 섬(1로 연결된 그룹)의 개수를 구하시오.

BFS 선택 이유: BFS는 한 번의 탐색으로 연결된 모든 영역을 빠르게 찾을 수 있음.

 

---

📌 BFS 선택 기준 정리

조건 ✅ BFS를 선택해야 하는 경우 ❌ DFS를 고려해야 하는 경우

조건	✅ BFS를 선택해야 하는 경우	❌ DFS를 고려해야 하는 경우
최단 거리 탐색	"최단 거리" 또는 "최소 이동 횟수" 문제	최단 거리 보장이 필요 없는 경우
가까운 노드부터 탐색	너비 우선 탐색이 필요한 경우	깊이 우선 탐색이 더 적합한 경우
단계별 탐색	K번 이동 후 도달 가능한 노드 찾기	모든 경로를 탐색해야 하는 경우
최소 횟수	"최소 몇 번의 이동"을 구하는 문제	백트래킹이 필요한 경우
모든 정점 탐색	그래프에서 연결된 모든 정점 찾기	깊이 있는 경로를 탐색해야 하는 경우

---

📌 BFS를 선택하는 사고 흐름 요약

1️⃣ "최단 거리" 또는 "최소 이동 횟수"를 찾는가? → BFS 적합

2️⃣ "가까운 곳부터 탐색"해야 하는가? → BFS 적합

3️⃣ "단계별 탐색"이 필요한가? → BFS 적합

4️⃣ "최소 횟수"를 찾는 문제인가? → BFS 적합

5️⃣ "모든 정점을 탐색"해야 하는가? → BFS 적합

---

📌 결론

✅ BFS는 최단 거리, 레벨 탐색, 연결 요소 탐색에 유리

✅ "최소 몇 번"이라는 표현이 들어간 문제라면 BFS가 적합

✅ 모든 정점을 탐색하는 경우 BFS가 DFS보다 효율적