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

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

20007번: 떡 돌리기

 

 

[ 문제풀이 ]

 

1. 이어진 집들을 입력받고, vector<pair<int, int>> list[ 1000 ]에 저장하고, visited[ 1000 ] 배열을 만들어 거리를 저장합니다.

 

2. 데이크스트라를 이용하여, Y부터 각 집까지의 거리를 visited 배열에 저장합니다.

 

3. visited 배열을 오름차순으로 정렬하고, for문을 통해 돌면서 거리 * 2의 값을 더해주면서 X를 넘으면 ans++를 해줍니다.

 

4. 이때, 거리 * 2의 값이 X보다 크다면 -1을 출력하고, 그렇지 않다면 ans + 1을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int N, M, X, Y;
vector<pair<int, int>> list[1000];
int visited[1000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> X >> Y;
 
    fill(visited, visited + N, -1);
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
 
        list[A].push_back({ B,C });
        list[B].push_back({ A,C });
    }
 
    priority_queue<pair<int, int>> pq;
 
    pq.push({ 0,Y });
 
    while (!pq.empty()) {
        const int cur = pq.top().second;
        const int cost = pq.top().first;
        pq.pop();
 
        if (visited[cur] == -1 || visited[cur] >= cost) {
            visited[cur] = cost;
        }
 
        for (auto& next : list[cur]) {
            int nextCost = next.second;
            int nextNode = next.first;
 
            if (visited[nextNode] == -1 || visited[nextNode] > cost + nextCost) {
                visited[nextNode] = cost + nextCost;
                pq.push({ cost + nextCost,nextNode });
            }
        }
    }
 
    sort(visited, visited + N);
 
    int cur = 0;
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        if (visited[i] * 2 > X) {
            cout << -1;
            return 0;
        }
        
        cur += visited[i] * 2;
 
        if (cur > X) {
            ans++;
            cur = visited[i] * 2;
        }
    }
 
    cout << ans + 1;
}