문제
자동차 경주로는 <그림 1>의 예와 같이 표현된다. 화살표는 각 지점을 잇는 도로를 의미하며 모든 도로는 일방통행 도로로 화살표 방향으로만 움직일 수 있다.
자동차 경주의 코스는 1번 지점에서 출발하여 다시 1번 지점으로 되돌아오는 것이다. 단, 중간에는 1번 지점을 지나서는 안 된다. 경주로는 1번 지점을 제외한 어느 지점에서 출발하여도 1번 지점을 지나가지 않고서는 같은 지점으로 돌아올 수 없도록 되어 있다. 또한 1번 지점에서 다른 모든 지점으로 갈 수 있고, 다른 모든 지점에서 1번 지점으로 갈 수 있다.
각 도로에는 <그림 2>의 예와 같이 그 도로를 지날 때 얻는 점수가 있다.
1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 팀이 우승을 하게 된다. 가장 많은 점수를 얻어 1번 지점으로 돌아오는 경로를 찾아 그 얻는 점수와 경로를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어지는데 이는 p번 지점부터 q번 지점으로 갈 수 있는 도로가 있고 그 도로에 부여된 점수가 r이라는 뜻이다. N은 1000이하의 자연수이고, p와 q는 1이상의 N이하의 자연수이며 r은 100이하의 자연수 이다. p와 q는 같지 않다.
출력
가장 많은 점수를 얻은 경로를 찾아, 첫째 줄에는 그 얻는 점수를 출력하고 둘째 줄에는 그 경로를 출력한다. 경로를 출력할 때는 지나는 지점들의 번호를 사이에 한 칸의 공백을 두어 출력한다. 출력하는 경로는 반드시 1번 지점에서 시작하여 1번 지점으로 끝나야 한다. 만약 같은 점수를 얻는 경로가 둘 이상일 경우 그 중 하나만 출력하면 된다.
풀이
문제 구조상 1번으로 돌아오는 경로를 제외하면 DAG처럼 처리할 수 있어서, 위상 정렬 기반 DP가 가능하다.
코드에서는 진입차수 degree[]를 이용해 1번에서 시작하는 위상 순회를 하며, 각 정점까지의 최대 점수 dp[]와 이전 정점 parents[]를 갱신한다. 어떤 간선을 통해 왔을 때 점수가 더 크면 그 간선이 현재 최적 경로가 된다.
여기서 중요한 구현 포인트는 1번 정점으로 들어오는 간선은 진입차수 계산에서 제외한다는 점이다. 그래야 출발점인 1번을 기준으로 나머지 구간을 DAG처럼 밀어낼 수 있다. 그렇지 않으면 사이클 때문에 일반적인 위상 정렬이 깨진다.
최대 점수만 구하면 끝나는 것이 아니라 실제 경로도 출력해야 하므로, 점수가 갱신될 때마다 parents[next] = cur를 함께 기록한다. 마지막에는 parents[]를 거꾸로 따라가면서 1번에서 1번으로 돌아오는 최적 경로를 복원하면 된다.
코드
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class Main {
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static int[] degree;
static ArrayList<Edge>[] adj;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
degree = new int[N + 1];
adj = new ArrayList[N + 1];
for (int i = 1; i <= N; i++)
adj[i] = new ArrayList<>();
while (M-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
adj[p].add(new Edge(q, r));
if (q != 1) degree[q]++;
}
System.out.println(solve());
}
static String solve() {
Queue<Integer> q = new ArrayDeque<>();
q.offer(1);
int[] dp = new int[N + 1];
int[] parents = new int[N + 1];
while (!q.isEmpty()) {
int cur = q.poll();
for (Edge edge : adj[cur]) {
int next = edge.to;
int weight = edge.weight;
if (dp[next] < dp[cur] + weight) {
dp[next] = dp[cur] + weight;
parents[next] = cur;
}
if (next != 1) {
degree[next]--;
if (degree[next] == 0)
q.offer(next);
}
}
}
ArrayDeque<Integer> result = new ArrayDeque<>();
int cur = 1;
result.addFirst(1);
while (parents[cur] != 1) {
cur = parents[cur];
result.addFirst(cur);
}
result.addFirst(1);
return String.valueOf(dp[1]) + '\n' +
result.stream()
.map(String::valueOf)
.collect(Collectors.joining(" "));
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
최대 점수 경로 문제지만, 위상 정렬이 가능하다는 점을 이용하면 훨씬 단순해진다. 점수 DP와 부모 추적을 같이 하면 경로 복원도 어렵지 않다.
