[BaekJoon][2611] 자동차 경주

BAEKJOON ONLINE JUDGE

한국정보올림피아드 시.도 지역본선 2004

2611 자동차 경주

https://www.acmicpc.net/problem/2611

최단경로 -> 최고 가중치(점수)를 구하는 문제

처음에는 다익스트라 알고리즘을 이용해서 풀었다.

경로 출력은 경로가 이전 지점을 저장하고 있기 때문에 재귀를 이용해서 거꾸로 출력하였다.

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
int n;
priority_queue <pair<int, int>> que;
vector<pair<int, int>> graph[1001];
int point[1001], road[1001];
 
void dijkstra()
{
    int weight, current, toWeight, to, i;
 
    que.push(make_pair(0, 1));
    while (!que.empty()) {
        weight = que.top().first;
        current = que.top().second;
        que.pop();
 
        if (weight >= point[current]) {
            for (i = 0; i < graph[current].size(); i++) {
                toWeight = graph[current][i].second + point[current];
                to = graph[current][i].first;
                if (point[to] < toWeight) {
                    point[to] = toWeight;
                    road[to] = current;
                    if(to != 1)
                        que.push(make_pair(toWeight, to));
                }
            }
        }
    }
}
 
void printRoad(int r)
{
    if (road[r] == 1) {
        printf("1 %d ", r);
        return;
    }
    printRoad(road[r]);
    printf("%d ", r);
}
 
int main()
{
    int m;
    int i, from, to, weight;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &from, &to, &weight);
        graph[from].push_back(make_pair(to, weight));
    }
 
    dijkstra();
 
    printf("%d\n", point[1]);
    printRoad(1);
 
    return 0;
}

두번 째는 DP로 풀었다.

1에서 출발하여 DP에 각 지점에서 출발하였을 때의 최대 점수를 저장하였다.

또한 1의 도착하는 경우에는 1이 아닌 저장될리 없는 n + 1로 값을 변경하여 저장하였고,

dp[n + 1] = 0으로 초기값을 넣어 주었다. (모든 경로는 1로 도착할 수 있다고 하였기 때문에 문제 없음)

또한, 한 번 방문했던 지점은 다시 방문하지 않아 circle을 방지하였다.

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
 
int n;
int dp[1002], road[1002];
vector<pair<int, int>> graph[1002];
 
int go(int idx)
{
    int i, weight;
 
    if (dp[idx] != -1)    return dp[idx];
    dp[idx] = 0;
 
    for (i = 0; i < graph[idx].size(); i++) {
        weight = go(graph[idx][i].first) + graph[idx][i].second;
 
        if (dp[idx] < weight) {
            dp[idx] = weight;
            road[idx] = graph[idx][i].first;
        }
    }
 
    return dp[idx];
}
 
void solve()
{
    int r = 1;
 
    memset(dp, -1, sizeof(dp));
    dp[n + 1] = 0;
 
    printf("%d\n", go(1));
 
    while (r <= n) {
        printf("%d ", r);
        r = road[r];
    }
    printf("1\n");
}
 
int main()
{
    int m;
    int i, from, to, weight;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &from, &to, &weight);
 
        if (to == 1)    to = n + 1;
        graph[from].push_back(make_pair(to, weight));
    }
 
    solve();
 
    return 0;
}