자동차 경주
Problem
https://www.acmicpc.net/problem/2611
Summary
단방향, 1번 지점에서 출발하여 가장 많은 점수를 얻어 다시 1번 지점으로 돌아오는 경로 및 점수를 구한다
Idea
dist[curr]: curr 에서의 최대 값 저장
dist[curr] = max(dist[curr], dist[next.to] + next.w)
dfs
- 1 -> 2 -> 5 -> 6 -> 8 -> 7 ->
4 -> 1
d[4] = max(d[4], d[1] + 6) = 6 - 1 -> 2 -> 5 -> 6 -> 8 ->
7 -> 4-> 1
d[7] = max(d[7], d[4] + 5) = 11 - 1 -> 2 -> 5 -> 6 ->
8 -> 7-> 4 -> 1
d[8] = max(d[8], d[7] + 4) = 15 - 1 -> 2 -> 5 ->
6 -> 8-> 7 -> 4 -> 1
d[6] = max(d[6], d[8] + 3) = 18
static void dfs1(int curr) {
for (V next : adj.get(curr)) {
if (dp[next.to] == 0) {
dfs1(next.to);
}
dp[curr] = Math.max(dp[curr], dp[next.to] + next.w);
}
}
f(curr): curr에서의 최대 값 으로 정의한다면
static int f(int curr) {
if (dist[curr] != -1) {
return dist[curr];
}
dist[curr] = 0;
for (V next : adj.get(curr)) {
int w = f(next.to) + next.w;
if (w > dist[curr]) {
dist[curr] = w;
trace[curr] = next.to;
}
}
return dist[curr];
}
bfs
dijkstra로 최고 가중치를 구하는 문제로 생각해 볼 수 있다
경로는 업데이트 할때마다 그 때의 이전 노드를 따로 저장 (즉, 어디서부터 왔는 가를 저장)하여
마지막엔 시작 노드로부터 그 역순으로 따라올라가면 경로를 얻을 수 있다.
s -> e 방향이면 trace[next] = curr;
e -> s 방향이면 trace[curr] = next;
static void bfs() {
Queue<V> q = new PriorityQueue<V>();
q.add(new V(1, 0));
boolean looped = false;
trace[1] = 1;
while (!q.isEmpty()) {
V curr = q.poll();
if (curr.to == 1) {
if (looped) {
continue;
}
looped = true;
}
for (V next : adj.get(curr.to)) {
if (dist[curr.to] + next.w > dist[next.to]) {
dist[next.to] = dist[curr.to] + next.w;
q.add(new V(next.to, dist[next.to]));
trace[next.to] = curr.to;
}
}}
}
System.out.println(dist[1]);
// LIFO
Stack<Integer> st = new Stack<Integer>();
st.push(1);
st.push(trace[1]);
int last = trace[1];
while (last != 1) {
last = trace[last];
st.push(last);
}
while (!st.isEmpty()) {
System.out.print(st.pop() + " ");
}
}