dfs+dp 문제 모음

DFS와 DP를 함께 사용하는 문제 유형은 최적 경로 탐색, 특정 상태에서의 최적화 문제, 또는 경로 개수를 구하는 문제에 자주 등장합니다. 아래는 DFS + DP를 사용하는 대표적인 문제와 관련 백준 문제 목록입니다.

---

1. 경로 탐색 및 최적화 문제

이 유형은 그래프나 격자에서 특정 조건에 맞는 경로를 찾거나, 경로의 수를 세거나, 경로의 최적값을 계산하는 문제입니다.

추천 문제

• 백준 1520 - 내리막 길
  DFS로 가능한 모든 경로를 탐색하고, DP로 중복 계산을 방지하여 경로 수를 효율적으로 계산.
• 백준 11403 - 경로 찾기
  그래프에서 특정 정점 간에 경로가 존재하는지 확인하는 문제로, DFS와 DP를 통해 경로 여부를 기록.
• 백준 1240 - 노드 사이의 거리
  그래프에서 두 노드 간의 거리를 구하는 문제로, DFS로 탐색하면서 DP에 거리 값을 저장.

---

2. 격자 기반 경로 문제

격자에서 특정 규칙을 따라 경로를 탐색하거나 최적화하는 문제입니다.

추천 문제

• 백준 1987 - 알파벳
  격자에서 알파벳을 중복 없이 이동하며 최대 경로를 탐색. DFS로 경로 탐색을 수행하고, DP로 방문 상태를 기록.
• 백준 14500 - 테트로미노
  격자에서 테트로미노 모양을 탐색하며 최대 점수를 찾는 문제로, DP와 DFS를 병행해 중복 계산을 방지.
• 백준 1937 - 욕심쟁이 판다
  격자에서 더 큰 값으로만 이동 가능한 경우, 최대 이동 가능한 칸 수를 계산. DFS로 경로 탐색, DP로 중복 계산 방지.

---

3. 트리 기반 문제

트리에서 특정 경로를 찾거나, 경로의 비용을 최소화하는 문제입니다.

추천 문제

• 백준 1949 - 우수 마을
  트리에서 "우수 마을"을 선정해 주민 수의 합을 최대화하는 문제로, DP와 DFS를 사용.
• 백준 2533 - 사회망 서비스(SNS)
  트리에서 "얼리 어답터"의 최소 수를 구하는 문제로, DP와 DFS를 병행.
• 백준 1167 - 트리의 지름
  트리에서 가장 긴 경로(지름)를 찾는 문제로, DFS와 DP를 사용.

---

4. 부분 문제 최적화

특정 상태에 도달하는 최적 경로를 구하거나, 특정 상태를 계산하는 문제입니다.

추천 문제

• 백준 1103 - 게임
  격자에서 이동 가능한 경로를 탐색하며 최적의 경로를 찾는 문제. DFS와 DP로 중복 계산 방지.
• 백준 12865 - 평범한 배낭
  배낭 문제의 확장으로, DFS로 가능한 모든 조합을 탐색하고 DP로 중복 계산을 줄이는 방식.

---

5. 백트래킹과 DP 결합 문제

DFS로 탐색하면서 조건을 만족하는 조합을 찾고, DP로 저장하여 계산을 줄이는 문제입니다.

추천 문제

• 백준 17070 - 파이프 옮기기 1
  격자에서 파이프를 옮기며 목적지까지 가는 경로의 수를 계산. DFS로 탐색하며 DP로 경로 수를 저장.
• 백준 9084 - 동전
  주어진 금액을 만드는 동전 조합의 수를 계산. DFS와 DP를 결합해 효율적으로 해결.
• 백준 2616 - 소형 기관차
  특정 조건에 맞는 구간 합의 최대값을 구하는 문제로, DFS와 DP를 병행.

---

문제를 효율적으로 학습하는 팁

1. 쉬운 문제부터 접근
   위 목록에서 실버→골드실버 → 골드실버→골드 순으로 난이도가 올라가므로, 익숙하지 않다면 쉬운 문제부터 풀어보세요.
2. DFS + DP의 원리 이해
   각 문제를 풀 때 DFS로 탐색하며 중복 계산을 줄이는 DP 로직을 직접 구현해보세요.
3. 유사한 문제 찾아보기
   백준에서 위 문제와 관련된 문제를 풀어보며 패턴을 익히세요.