1. 문제
위와 같은 유향 그래프가 주어졌을 때, 그래프를 탐색하며 정점의 값을 누적합하려면 어떻게 해야할까요?
2. 깊이 우선 탐색(DFS; Depth-First Search)
깊이 우선 탐색으로 값을 구하는 과정을 살펴봅시다.
먼저 더 이상 간선이 없는 정점까지 탐색 며 값을 누적합니다.
또 다른 경로를 탐색합니다.
그 결과 누적합 최대값은 65입니다.
물론, DFS로 이렇게 풀 수도 있으나 문제점이 보입니다.
값이 5와 25인 정점은 다른 경로라면 탐색을 했더라도 다시 탐색해야합니다.
이 문제를 해결하기 위해 다른 방법을 생각해봅시다.
3. 너비 우선 탐색(BFS; Breadth-First Search)
깊이 우선 탐색으로 경로마다 끝까지 탐색을 했더니 같은 정점을 여러 번 살펴봐야하는 문제가 있었습니다.
그래서 이번엔 너비 우선 탐색으로 풀어봅시다.
너비 우선 탐색 과정을 거치면 값이 5인 정점에서 만나게 됩니다.
이때, 더 큰 값을 취하여 과정을 이어가면, 값이 25인 정점은 두 번 탐색할 필요 없이 한 번에 최대값 65를 알 수 있습니다.
그렇다면 너비 우선 탐색이 정답일까요?
아닙니다. 너비 우선 탐색을 시작할 때, 우리는 값이 15인 정점이 출발점이라는 것을 당연하게 생각하였습니다.
그러나 출발점은 들어오는(inbound) 간선이 없는 정점이 되어야 하고, 그런 정점을 알기 위해서는 모든 간선을 탐색해야 알 수 있습니다.(깊이 우선 탐색도 같은 문제를 가지고 있습니다.)
그렇다면 정답은 무엇일까요?
3. 위상 정렬
위상 정렬된 정점을 차례로 탐색하면서 dp테이블 값을 변경시켜나가는 방법이 있습니다.
각 정점의 dp테이블 초기값을 다음과 같이 설정합니다.
| 정점 | 15 | 10 | 20 | 5 | 25 |
| value | 15 | 10 | 20 | 5 | 25 |
점화식은 다음과 같습니다.
dp[next] = max( dp[next], (dp[currunt] + next 정점의 값) )
위상 정렬된 첫 번째 정점인 값이 15인 정점을 탐색하면 dp테이블은 다음과 같이 수정됩니다.
| 정점 | 15 | 10 | 20 | 5 | 25 |
| value | 15 | 25 | 35 | 5 | 25 |
다음으로 값이 10인 정점을 탐색하면 dp테이블은 다음과 같이 수정됩니다.
| 정점 | 15 | 10 | 20 | 5 | 25 |
| value | 15 | 25 | 35 | 30 | 25 |
다음으로 값이 20인 정점을 탐색하면 점화식에 의해 더 큰 값으로 교체됩니다.
| 정점 | 15 | 10 | 20 | 5 | 25 |
| value | 15 | 25 | 35 | 40 | 25 |
마지막으로 값이 5인 정점을 탐색하면 원하는 결과값 65가 기록됩니다.
| 정점 | 15 | 10 | 20 | 5 | 25 |
| value | 15 | 25 | 35 | 40 | 65 |
