[백준] 20007번 떡 돌리기 (C++)

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

 

 

이 문제는 0부터 N-1까지의 노드가 주어지고 M개의 간선(+ 가중치)에 따라 연결관계가 주어질때 X만큼을 넘지 않으면서 모든 노드에

떡을 나눠주었을때 걸리는 최소 일 수를 구하는 문제이다.

 

주어진 문제에서 핵심적으로 봐야할 부분은 떡은 한번에 하나씩만 들 수 있는 것이다

따라서 시작점에서 다른노드로 갔을경우 무조건 다시 시작점으로 돌아가야지 떡을 다시 나눠줄 수 있다.

 

이 문제를 해결할때 저 문장을 자세히 안봐서 풀기 되게 까다로웠다...

 

따라서

1. 시작점에서 다익스트라 알고리즘을 사용하여 모든 노드에 갈 수 있는 최단거리(비용)을 구한다.

2. 시작점을 제외한 비용값 * 2를 최소힙에 넣는다.

3. 최소 비용들을 계속 더하면서 X를 넘을때 일수를 증가시키며 다시 합한다.

 

 

테스트케이스 1번을 사진과 같이 보면 이해가 쉽다.

 

 

이 문제에서의 핵심은 시작점에서 모든 노드를 도착했을때 최소 비용을 구했을때(가기만 할때)

X 2를 하였을때(왕복 비용)

 

즉 X2를 했을때를 구하여 최소 일수를 세주는 것이 핵심이였다.

 

정답 코드

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

int dx[] = {0, 1, -1, 0, 1, -1, -1, 1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int N, M, X, Y;
vector<vector<pii>> v(1001);
int dist[1001];

void dijkstra(int a) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[a] = 0;
    pq.push({0, a});        // 비용, 노드

    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 = cost + it.second;

            if(dist[nextNode] > nextcost) {
                pq.push({nextcost, nextNode});
                dist[nextNode] = nextcost;
            }
        }
    }
}

void Init() {
    for(int i = 0; i < N; i++) {
        dist[i] = MAX;
    }
}

void solve() {
    dijkstra(Y);

    priority_queue<int, vector<int>, greater<int>> pq;

    for(int i = 0; i < N; i++) {
        dist[i] *= 2;
    }

    for(int i = 0; i < N; i++) {
        if(i != Y) {
            pq.push(dist[i]);
        }
    }

    int tmp = 0;
    int cnt = 0;

    while(!pq.empty()) {
        int x = pq.top();
        pq.pop();

        if(x > X) {
            cout << -1;
            return;
        }

        if(tmp + x> X) {
            tmp = 0;
            cnt++;
        }

        tmp += x;
    }

    if(tmp > 0) cnt++;

    cout << cnt;
}

void input() {
    cin >> N >> M >> X >> Y;

    Init();

    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();
}