모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice

🥏동적계획법 역추적

• 현재 해(최종 해)를 구하기까지의 경로를 역으로 추적하는 것
• 기존 동적 계획법과 동일한 풀이에 경로를 저장하는 부분만 추가
• 최종 해가 존재하는 위치에서 시작해서 저장한 경로값을 따라 추적

---

📉경로 저장방법

배열활용
: 경로 배열(path)을 만들어서 DP배열의 값이 갱신될때 사용한 과거의 해의 위치를 저장.

[예시]

📗대표문제

BOJ) 14002 가장 긴 증가하는 부분 수열 4

해결전략

DP+역추적

• 수열을 0번 인덱스부터 탐색하며 해당 인덱스로 끝나는 '증가하는 부분수열' 길이의 최댓값을 계산.
• 최댓값이 갱신될때 어느 원소에서 온건지 경로(인덱스)를 Path배열에 저장.

---

🔀최단거리 역추적

• 최단 거리를 구하기 까지의 경로를 역으로 추적하는 것
• 기존 BFS와 동일한 풀이에 경로를 저장하는 부분만 추가
• 도착 정점에서 시작해서 저장한 경로값을 따라 추적 -> back 함수.

❔ 경로는 어떻게 저장하지?

1. 배열 활용

• 경로 배열을 만들어서 탐색하는 자식노드에 부모노드의 위치를 저장
• 노드를 배열의 인덱스로 표현할 수 있는 경우 사용

2. 큐 활용

• 탐색에 사용하는 큐를 pair로 만들어 누적 경로를 저장
• 메모리가 많이 소요될 수 있음

---

📗대표문제

BOJ) 13913 숨바꼭질4

---

🔭다익스트라 역추적

• 기존 다익스트라 알고리즘에 경로를 추적하는 부분이 추가된것.
• dist값이 갱신될때 path배열에 이전노드(부모노드)의 index를 저장하자.
• 만일 1번 -> 5번 까지의 최단경로가 궁금하다면
  5 -> path[5]=4 ->path[4]=1 ->path[1]=0 break.
  즉 1->4->5의 순서로 최단경로를 이루는 것을 알 수 있다.

✨마무리

• 역추적은 기존 알고리즘에서 구한 해의 경로를 추적하는 것
• 기존 풀이에 경로를 저장하는 부분과 추적하는 부분만 추가하면 됨.
• 주로 동적계획법(DP), 최단거리(BFS), 최단경로(다익스트라,플로이드-워셜)와 같이 나옴.
• 경로 저장은 배열로 구현
• 나중에 경로를 추적해야 하므로 위치(인덱스)를 저장

💡이것도 알아보세요

• 최단 거리 역추적 문제는 경로를 큐를 통해 저장할 수 도 있어요. 배열로 경로를 저장하는 것과 다른점이 무엇일까요?