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

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

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

DFS는 백트래킹, 그래프 탐색, 특정 조건을 만족하는 경로 탐색에 적합합니다.

---

Step 1: 문제에서 "완전 탐색"이 필요한가?

✅ DFS는 완전 탐색(모든 경우를 다 살펴야 하는 경우)에 적합

✅ 주어진 문제에서 모든 가능한 경우의 수를 고려해야 하는지 확인

• 예시
  •   미로에서 도달 가능한 모든 경로 찾기
  •   재귀적으로 가능한 모든 조합 찾기 (순열, 부분집합 등)

📌 예제 문제

문제: N×N 미로에서 출발점에서 도착점까지 가는 모든 가능한 경로를 찾으시오.

DFS 선택 이유: 여러 갈래의 경로를 모두 탐색해야 하므로 완전 탐색이 필요함.

---

Step 2: 그래프 탐색 문제인가?

✅ DFS는 그래프 탐색에서 "깊이 우선 탐색"이 필요할 때 적합

✅ 그래프의 모든 노드를 탐색해야 하는지 확인

• 예시
  •   사이클 탐색 (DFS로 방문한 노드를 추적하여 사이클 감지)
  •   특정 노드에서 다른 노드까지의 경로 탐색 (백트래킹)
  •   연결 요소 개수 찾기 (연결된 그래프 덩어리 찾기)

📌 예제 문제

문제: 주어진 그래프에서 "연결된 요소의 개수"를 구하시오.

DFS 선택 이유: 한 노드에서 연결된 모든 노드를 방문하며 한 덩어리를 탐색할 때 DFS가 유리.

---

Step 3: 백트래킹(Backtracking)이 필요한가?

✅ 백트래킹은 "모든 경우의 수를 탐색하되, 불필요한 탐색은 가지치기"하는 기법

✅ 경우의 수가 너무 많아 DFS로 탐색하면서 가지치기가 필요한 경우

• 예시
  •   N-Queen 문제 (불가능한 경우를 가지치기하며 탐색)
  •   모든 조합 및 순열 찾기 (예: 사전순으로 모든 가능한 문자열 생성)
  •   특정 조건을 만족하는 경로 찾기 (예: 특정 합을 만족하는 부분 집합 찾기)

📌 예제 문제

문제: 8×8 체스판에서 N-Queen을 배치하는 방법을 모두 찾으시오.

DFS 선택 이유: 체스판에서 가능한 배치를 하나씩 탐색하며 가지치기해야 함 (백트래킹 활용).

---

Step 4: DFS vs BFS 비교 (최단 거리 문제인가?)

✅ DFS는 깊이 우선 탐색이므로 "최단 거리" 탐색에는 부적합

✅ 문제에서 "최단 경로"를 찾으라고 하면 BFS를 고려해야 함.

• 예시
  •   최단 거리(미로에서 가장 빠른 길 찾기) → BFS가 유리
  •   모든 가능한 경로 탐색 (도달 가능한 모든 경로 찾기) → DFS가 유리

📌 예제 문제

문제: 미로에서 출발점에서 도착점까지 가는 가장 짧은 경로의 길이를 구하시오.

DFS 선택 ❌ → BFS 선택 ✅

이유: BFS는 최단 거리 탐색에 더 적합 (레벨별 탐색이 가능).

---

Step 5: 트리(재귀적 구조)가 주어졌는가?

✅ 트리 구조에서는 DFS(재귀 탐색)가 자연스러운 선택

✅ 문제에서 "재귀적으로 탐색"해야 하는 경우 DFS가 적합

• 예시
  •   이진 트리에서 특정 경로 찾기
  •   트리에서 특정 조건을 만족하는 모든 경로 찾기
  •   트리에서 LCA(최소 공통 조상) 찾기

📌 예제 문제

문제: 이진 트리에서 루트에서 리프까지 가는 모든 경로를 출력하시오.

DFS 선택 이유: 트리는 재귀적으로 탐색하는 것이 자연스러우며, 깊이 우선 탐색이 적합.

---

📌 DFS 선택 기준 정리

조건	✅ DFS를 선택해야 하는 경우	❌ BFS를 고려해야 하는 경우
완전 탐색	모든 경우의 수를 탐색해야 하는 문제	불필요한 경우의 수가 많아 최적화 필요
그래프 탐색	사이클 감지, 경로 탐색, 연결 요소 찾기	최단 경로를 찾는 문제
백트래킹	가능한 모든 경우를 탐색하면서 가지치기	단순한 최단 거리 문제
최단 거리	❌ DFS는 비효율적	✅ BFS가 유리
트리 구조	재귀적으로 탐색해야 하는 경우	특정 노드 간 거리 찾기

---

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

1️⃣ 문제가 완전 탐색(모든 경우의 수 탐색)이 필요한가? → DFS 적합

2️⃣ 그래프 탐색 문제인가? → 경로 찾기나 연결 요소 문제라면 DFS 적합

3️⃣ 백트래킹(불필요한 탐색 가지치기)이 필요한가? → DFS 적합

4️⃣ 최단 경로 문제인가? → DFS ❌, BFS ✅

5️⃣ 트리 구조인가? → DFS 적합 (재귀적 탐색이 자연스러움)

---

📌 결론

✅ DFS는 그래프 탐색, 완전 탐색, 백트래킹, 트리 문제에서 유리

✅ 최단 거리 문제라면 DFS 대신 BFS를 고려

✅ 문제 유형에 따라 DFS/BFS를 적절히 선택하는 것이 중요