[백준] 13905번 세부 (C++)

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

 

 

이 문제는 노드와 간선이 주어졌을때 시작 노드에서부터 출발하여 도착노드까지 최대의 빼빼로를 가지고 도착할 수 있는 개수를 출력하는 문제이다.

 

여기서 중요한 것은 간선의 가중치인데 노드에서 노드로 이동할때 간선의 가중치만큼 최대의 빼빼로를 가지고 이동할 수 있다.

 

문제를 해결하기 위해서 현재 노드에서부터 욕심내어서 간선을 찾아서 가면 어떨까를 생각하였다 즉 그리디하게 가중치가 높은 간선만을 가면 자연스럽게 최댓값이 나올것이라고 생각하여

 

최대힙 다익스트라 알고리즘을 구현하였다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N, M, s, e;
vector<vector<pii>> v(100001);
int dist[100001];

void dijkstra(int start) {
    priority_queue<pii, vector<pii>> pq;
    pq.push({MAX, start});
    dist[start] = MAX;

    while(!pq.empty()) {
        int Node = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        if(dist[Node] > cost) continue;

        for(auto it : v[Node]) {
            int nextNode = it.first;
            int nextCost = min(cost, it.second);

            if(dist[nextNode] < nextCost) {
                dist[nextNode] = nextCost;
                pq.push({nextCost, nextNode});
            }
        }
    }
}

void solve() {
    dijkstra(s);

    cout << dist[e];
}

void input() {
    cin >> N >> M >> s >> e;

    for(int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

코드 설명

void dijkstra(int start) {
    priority_queue<pii, vector<pii>> pq;
    pq.push({MAX, start});
    dist[start] = MAX;

    while(!pq.empty()) {
        int Node = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        if(dist[Node] > cost) continue;

        for(auto it : v[Node]) {
            int nextNode = it.first;
            int nextCost = min(cost, it.second);

            if(dist[nextNode] < nextCost) {
                dist[nextNode] = nextCost;
                pq.push({nextCost, nextNode});
            }
        }
    }
}

 

가장 핵심인 다익스트라 함수를 보면 초기에 최댓값과 노드를 넣어주었다 이것의 의미는 {최대로 갖고 갈 수 있는 빼빼로의 개수, 현재 노드}

갈 수 있는 노드를 확장하는데 nextCost 변수를 확인하면 간선을 사용해서 노드를 이동할때 확장하기 전 빼빼로의 개수와 확장되었을때 빼빼로의 개수중 작은 값 즉 간선을 사용했을때 작은것으로 수렴되므로 최소값으로 갱신해주었다.