그래프에서 최단거리는 경우에 따라 BFS, 다익스트라, 벨만 포드, 플로이드 와샬을 사용하여 구할 수 있다. 그렇다면 최장거리는 어떻게 구할 수 있을까?
사이클이 없는 무향 그래프(트리)에서 최장거리
트리에서는 어떤 두 노드를 선택해도 둘 사이의 경로가 항상 하나만 존재한다. 따라서 BFS을 이용하여 구할 수 있다.
사이클이 없는 유향 그래프에서 최장거리
일반적인 그래프에서 최장거리를 구하는 방법은 NP-Hard로 알려져 있다. 하지만 DAG(Directed Acyclic Graph)에서는 구할 수 있다. DAG에서 최장거리를 구할 수 있는 2가지 방법을 정리해보자.
동적 계획법
정점 $u$ → $v$의 최장거리를 구하는 점화식을 아래와 같이 세워보자.
$$ D[i] = \text{정점 } i \text{ 에서} v \text{ 까지의 최장거리} $$
\(G(x)= {\{\ w\ |\ (w, x)\in E\ \}}\)을 정점 \(x\)에서 나가는 정점의 집합이라고 하면 \(D[i]\)은 아래와 같다.
$$ D[i] = max(\{D[G(i)] + cost(i, G(i)) \}) $$
예를 들어 정점 \(i\)의 인접한 정점을 \(j\)라고 하면 \(D(i)\)의 의미는 아래와 같다.
$$ i \text{에서 } v \text{까지 최장거리} = j \text{에서 } v \text{까지 최장거리} + i \text{에서 } j \text{까지 거리}$$
문제
[G2] 메이플스토리
DAG가 아닌 것 같지만, 사냥터 \(i\)에서 사냥터 \(j\)로 이동한 것은 사냥터 \(j\)가 경험치가 더 높기 때문이다. 그렇다면 다시 \(j\)에서 \(i\)로 오는 경우는 경험치가 손해이기 때문에 존재하지 않는다. 따라서 DAG이므로 DP로 해결할 수 있다.
D[time][here] : time동안 here에서 얻은 최대 경험치
[G2] 스키장
임의 지점 \(i\)에서 \(T\)번 지점까지의 최장시간을 구해야 한다. 스키는 스키 코스 번호가 감소하는 방향으로, 리프트는 증가하는 스키 코스 번호가 증가하는 방향으로 탈 수 있다. 리프트를 타는 것은 그래프의 사이클이 발생하는 것이 아닌 증가한 리프트 횟수에 대한 다른 그래프의 상태변화이다. 따라서 리프트 회수가 같은 그래프에서는 한 번 방문한 스키 코스에 다시 방문할 수 없으므로 주어진 문제는 DAG이다. 이 문제는 그래프가 1개가 아니라 리프트의 횟수만큼 차원이 있는 것이라 판단할 수 있다
D[count][here] : count번 리프트를 타고 here지점에 왔을 때 최장 스키 시간
위상 정렬
일반적인 그래프에서 단일 정점에 대한 최단 경로를 구하는 알고리즘은 \(O(E\ logV)\)의 시간 복잡도를 갖는 다익스트라 알고리즘이 있다. DAG에서는 위상 정렬을 이용해 \(O(V+E)\)에 위상 순서에 따라 경로를 갱신해 최단거리를 구할 수 있다.
- 주어진 DAG를 위상 정렬한다.
- 시작 정점은 0, 나머지는 무한으로 거리 배열을 초기화한다.
- 각 노드 별 모든 간선에 대해 edge relaxation 한다.
따라서 그래프의 가중치를 음수로 바꾸면 최장거리를 구할 수 있다.
문제
최장거리 및 간선 역추적해야 한다. 위상 정렬을 이용해 최장거리를 구하고, dist[here] = dist[prev] + cost를 만족하는 prev를 따라 역추적하면 된다.