DFS, BFS, 다익스트라, DFS+DP, 백트래킹 문제 유형 정리

DFS, BFS, 다익스트라, DFS+DP, 백트래킹 문제 유형 정리

문제에서 사용해야 할 알고리즘 유형은 입력 범위, 문제 요구사항, 시간 복잡도, 그래프 구조를 기준으로 구별할 수 있습니다. 아래는 각 유형의 특징, 시간 복잡도, 입력 범위, 적용 예시, 구별 기준을 한눈에 정리한 표입니다.

---

1. DFS (Depth-First Search)

• 특징:
  • 한 경로를 끝까지 탐색한 뒤, 백트래킹하면서 다른 경로를 탐색.
  • 트리나 그래프의 경로 조사, 특정 조건을 만족하는 경로 찾기.
• 시간 복잡도:
  • 그래프 전체 탐색: O(V+E)O(V + E)O(V+E) (V: 정점, E: 간선).
  • 경우의 수 탐색: O(2N)O(2^N)O(2N) (예: 모든 경로 탐색).
• 입력 범위:
  • 노드 수 V≤103V \leq 10^3V≤103 (그래프가 작을 때).
  • N≤15−20N \leq 15-20N≤15−20 (모든 경우의 수를 완전 탐색할 때).
• 적용 예시:
  • 미로 탐색, 특정 경로 존재 여부 확인.
  • 그래프에서 조건을 만족하는 경로 탐색.
• 구별 기준:
  • "특정 조건을 만족하는 경로"를 찾는 문제.
  • 그래프/트리 문제이며, 모든 경로를 확인해도 시간이 충분한 경우.

---

2. BFS (Breadth-First Search)

• 특징:
  • 최단 거리(가중치가 동일할 때)를 구하거나, 계층적으로 탐색.
  • 탐색 순서가 중요하고, 첫 번째로 발견한 해답이 최적일 때 사용.
• 시간 복잡도:
  • O(V+E)O(V + E)O(V+E) (V: 정점, E: 간선).
• 입력 범위:
  • 노드 수 V≤104V \leq 10^4V≤104.
  • 간선 수 E≤105E \leq 10^5E≤105.
• 적용 예시:
  • 미로에서 최소 칸 수로 이동.
  • 특정 조건을 만족하는 최단 거리 확인.
• 구별 기준:
  • "최단 거리" 문제이며, 가중치가 없는 그래프에서 사용.
  • 탐색이 계층적으로 진행되어야 하는 문제.

---

3. 다익스트라 (Dijkstra)

• 특징:
  • 가중치가 있는 그래프에서 최단 경로를 구하는 알고리즘.
  • 우선순위 큐를 사용해 효율적으로 구현.
• 시간 복잡도:
  • O((V+E)log⁡V)O((V + E) \log V)O((V+E)logV) (우선순위 큐 사용 시).
• 입력 범위:
  • 노드 수 V≤104V \leq 10^4V≤104.
  • 간선 수 E≤105E \leq 10^5E≤105.
• 적용 예시:
  • 가중치가 있는 지도에서 출발점에서 도착점까지의 최소 비용.
  • 예: "1번 도시에서 모든 도시로 이동하는 최소 거리".
• 구별 기준:
  • 가중치가 있는 그래프에서 최단 경로를 찾는 문제.

---

4. DFS + DP (Memoization)

• 특징:
  • DFS로 탐색하며 중복 계산을 줄이기 위해 DP(Memoization)를 사용.
  • 최적화 문제에서 효율적인 탐색 가능.
• 시간 복잡도:
  • 중복 계산을 줄이면 O(N)O(N)O(N) 또는 O(V)O(V)O(V) 수준.
• 입력 범위:
  • 노드 수 V≤105V \leq 10^5V≤105 (그래프 문제).
  • 상태 수 N≤100N \leq 100N≤100 (DP 문제).
• 적용 예시:
  • 특정 조건을 만족하는 경로의 최대/최소 값 구하기.
  • 그래프나 트리에서 최적 경로 탐색.
• 구별 기준:
  • 최적 경로 탐색 중 중복 계산이 많고, 이를 줄이기 위해 DP가 필요한 문제.

---

5. 백트래킹

• 특징:
  • 탐색 중 불필요한 경로를 가지치기(Pruning)하며 모든 경우를 조사.
  • DFS와 유사하지만, 가지치기 조건으로 불필요한 계산을 줄임.
• 시간 복잡도:
  • 최악의 경우 O(2N)O(2^N)O(2N) 또는 O(N!)O(N!)O(N!).
• 입력 범위:
  • 상태 수 N≤15−20N \leq 15-20N≤15−20 (완전 탐색이 가능할 때).
  • 상태 가지 수가 많을 경우 N≤10N \leq 10N≤10.
• 적용 예시:
  • N-Queen, 조합/순열 생성 문제.
  • 제약 조건을 만족하는 최적 경로 찾기.
• 구별 기준:
  • "모든 경우의 수"를 탐색해야 하지만, 가지치기를 통해 효율성을 높일 수 있는 문제.

---

입력 범위와 알고리즘 선택 요약

입력 범위알고리즘 유형특징

V,E≤103V, E \leq 10^3V,E≤103	DFS, BFS	탐색 가능한 그래프가 작음. 모든 경로를 완전 탐색 가능.
N≤15−20N \leq 15-20N≤15−20	DFS, 백트래킹	모든 경우의 수를 완전 탐색할 때. 2N2^N2N 또는 N!N!N! 수준의 탐색.
V,E≤104−105V, E \leq 10^4 - 10^5V,E≤104−105	BFS, 다익스트라	그래프가 크지만 O(V+E)O(V + E)O(V+E) 또는 O((V+E)log⁡V)O((V + E) \log V)O((V+E)logV) 알고리즘으로 해결 가능.
V,E≥105V, E \geq 10^5V,E≥105	DFS + DP, 특수 알고리즘 (플로이드-와샬 등)	입력 크기가 커서 DP나 최적화 알고리즘 필요.
N>20N > 20N>20, 2N2^N2N, N!N!N!	불가능 또는 특수한 최적화 필요	입력 크기가 커서 완전 탐색으로는 처리 불가능. 최적화 알고리즘(탐욕법 등) 검토 필요.

---

문제 유형별 접근 요령

1. 그래프/트리 문제:
   • V,E≤104V, E \leq 10^4V,E≤104: DFS, BFS.
   • 가중치가 있으면 다익스트라.
   • 최적 경로 탐색 + 중복 계산 많으면 DFS + DP.
2. 경우의 수 문제:
   • N≤15−20N \leq 15-20N≤15−20: DFS, 백트래킹.
   • 조합/순열 생성이나 가지치기가 필요한 문제는 백트래킹.
3. 최단 거리 문제:
   • 가중치가 없으면 BFS.
   • 가중치가 있으면 다익스트라.
4. 최적화 문제:
   • 입력 크기가 크고 중복 계산이 많다면 DFS + DP.

문제의 요구사항과 입력 크기를 함께 고려하면 올바른 알고리즘을 쉽게 선택할 수 있습니다.