백준 - 10217 KCM Travel

문제 링크입니다 : https://www.acmicpc.net/problem/10217

10217번: KCM Travel

 

다익스트라문제에서 2개 조건을 고려해야 하는 문제였다.

 

우선순위 큐로 최단경로를 찾다가 cost가 M보다 커져서 끝내게 되었을 때, 그 경로까지 이동하면서 지나오면서 구해놓은 각 지점별 거리값은 의미가 없어진다. 그래서 이차원 배열 형태 (dist)로 cost별로 탐색하도록 했다.

 

입력

1
5 5 4
1 2 2 1
2 3 2 1
3 5 2 1
1 3 1 5

 

출력

6

 

위의 결과가 정상적으로 나와야 옳바른 프로그램이다.

 

 

이 문제에서 하나 더 건진 아이디어는 이렇게 2차원 배열형태로 매번 경우를 나눠서 탐색할 때, 최적화 하는 기법을 익혔다.

첫 번째 코드는 순수하게 내가 짠 코드라서 최적화 기법이 적용되어 있지 않다. 그런데 맞은 사람들의 코드를 보니 단 몇줄로 꽤 괜찮은 최적화를 해냈다.

두 번째 코드가 다른 사람들 코드를 보고 익힌 최적화 기법을 적용한 것이다.

 

현재 큐에 넣을 cost 값보다 높은 부분들은 현재 넣는 cost값보다 작거나 같은 거리 값을 가질 수 있다. 따라서 현재 cost값보다 큰 부분에서 현재 dist보다 크다면 다 덮어써주면 가지치기를 하는 효과를 얻을 수 있다.

 

 

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;

int T, N, M, K;

// distance, cost, location
vector<vector<pair<pair<int, int>, int>>> board;
//distance
vector<vector<int>> dist;

int dijkstra(int start) {
    // distance, cost, location
    priority_queue<pair<pair<int, int>, int>> pq;
    dist[start][0] = 0;
    pq.push({{0, 0}, start});

    while(!pq.empty()) {
        int cur = pq.top().second;
        int curDist = -pq.top().first.first;
        int curCost = -pq.top().first.second;
        pq.pop();

        if(dist[cur][curCost] < curDist) continue;
        if(curCost > M) continue;

        if(cur == N) return curDist;
        // cout << curCost << '\n';



        for(int i = 0; i < board[cur].size(); i++) {
            int next = board[cur][i].second;
            int nextDist = board[cur][i].first.first + curDist;
            int nextCost = board[cur][i].first.second + curCost;
            // cout << nextCost << '\n';
            if(nextCost > M) continue;
            if(nextDist < dist[next][nextCost]) {
                dist[next][nextCost] = nextDist;
                pq.push({{-nextDist, -nextCost}, next});
            }

        }

    }

    return -1;
}


int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    cin >> T;
    for(int tCase = 0; tCase < T; tCase++) {
        cin >> N >> M >> K;

        if(N == 1) {
            cout << "0\n";
        } else if(K == 0) {
            cout << "Poor KCM\n";
        }

        
        // {pos, {cost, distance}}
        board.assign(N + 1, vector<pair<pair<int, int>, int>>());
        dist.assign(N + 1, vector<int>(M + 1, INF));

        int u, v, c, d;
        for(int i = 0; i < K; i++) {
            cin >> u >> v >> c >> d;
            board[u].push_back({{d, c}, v});
        }

        int temp = dijkstra(1);
        if(temp == -1) {
            cout << "Poor KCM\n";
        } else {
            cout << temp << '\n';
        }
        

    }


    return 0;
}

 

 

 

최적화 적용

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;

int T, N, M, K;

// distance, cost, location
vector<vector<pair<pair<int, int>, int>>> board;
//distance
vector<vector<int>> dist;

int dijkstra(int start) {
    // distance, cost, location
    priority_queue<pair<pair<int, int>, int>> pq;
    dist[start][0] = 0;
    pq.push({{0, 0}, start});

    while(!pq.empty()) {
        int cur = pq.top().second;
        int curDist = -pq.top().first.first;
        int curCost = -pq.top().first.second;
        pq.pop();

        if(dist[cur][curCost] < curDist) continue;
        if(curCost > M) continue;

        if(cur == N) return curDist;
        // cout << curCost << '\n';



        for(int i = 0; i < board[cur].size(); i++) {
            int next = board[cur][i].second;
            int nextDist = board[cur][i].first.first + curDist;
            int nextCost = board[cur][i].first.second + curCost;
            // cout << nextCost << '\n';
            if(nextCost > M) continue;
            if(nextDist < dist[next][nextCost]) {


                // 최적화 부분 - 시작
                for(int j = nextCost + 1; j <= M; j++) {
                    if(dist[next][j] <= nextDist) break;
                    dist[next][j] = nextDist;
                }
                // 최적화 부분 - 끝

                dist[next][nextCost] = nextDist;
                pq.push({{-nextDist, -nextCost}, next});
            }

        }

    }

    return -1;
}


int main() {
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);
    cin >> T;
    for(int tCase = 0; tCase < T; tCase++) {
        cin >> N >> M >> K;

        if(N == 1) {
            cout << "0\n";
        } else if(K == 0) {
            cout << "Poor KCM\n";
        }

        
        // {pos, {cost, distance}}
        board.assign(N + 1, vector<pair<pair<int, int>, int>>());
        dist.assign(N + 1, vector<int>(M + 1, INF));

        int u, v, c, d;
        for(int i = 0; i < K; i++) {
            cin >> u >> v >> c >> d;
            board[u].push_back({{d, c}, v});
        }

        int temp = dijkstra(1);
        if(temp == -1) {
            cout << "Poor KCM\n";
        } else {
            cout << temp << '\n';
        }
        

    }


    return 0;
}

 

 

 

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~