[백준] 20007 - 떡 돌리기

1. 문제 이해

N개의 집과 각 집들을 이어주는 M개의 양방향 도로가 있다.

 

시작점과 하루에 이동할 수 있는 거리가 주어졌을 때, 모든 정점을 방문하기 위한 최소 소모 날짜를 구해야 한다. 이 때, 떡은 한번에 하나씩만 들고갈 수 있으므로, 특정 집을 방문하면 반드시 시작점으로 돌아와야 한다. ( 떡 다시 들기 위해서 )

 

최소 소모 날짜를 구해야 하므로, 시작점에서 다른 정점까지의 최소 거리를 구하면 된다. 즉, 다익스트라 알고리즘을 사용하면 된다.

---

2. 문제 풀이

문제 입력에 따라 양방향 도로가 존재하는 그래프를 구현한다. 그리고 다익스트라 알고리즘을 이용하면 시작점에서 다른 모든 정점까지의 최소 거리를 구할 수 있다.

 

거리가 가까운 집 부터 방문한다고 했으므로 정렬을 한다. 그리고, 하루에 X보다 더 먼거리를 걷지 않도록 하면서 소요되는 날짜를 구한다. 이 때, 단순하게 모든 거리를 구하고, X로 나누면 안된다.

 

만약 걸어야 하는 거리가 8, 10, 12 이고 X가 15라고 하면, 전부 더한값을 X로 나누면 2가 나온다.

그러나, 하나씩 계산해보면 하루에 하나의 집밖에 방문하지 못하므로 3이 나온다.

 

---

3. 제출 결과

---

4. 문제 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 2e9
using namespace std;
vector<pair<int,int>> graph[1001];

int dijkstra(int start, int n, int lim) {
    vector<int> dist(n, INF);
    dist[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    pq.push(make_pair(0, start));
    
    while(!pq.empty()) {
        int here = pq.top().second;
        int cost = pq.top().first;

        pq.pop();
        if(dist[here] < cost) {continue;}
        for(int i=0; i<graph[here].size(); i++) {
            int there = graph[here][i].first;
            int thereCost = cost + graph[here][i].second;

            if(dist[there] > thereCost) {
                dist[there] = thereCost;
                pq.push(make_pair(thereCost, there));
            }
        }
    }
    sort(dist.begin(), dist.end());
    int cnt = 0, ans=1;
    for(int i=0; i<n; i++) {
        if(dist[i] == INF || dist[i] * 2 > lim) {
            return -1;
        } else {
            if(cnt + (dist[i]*2) > lim) {
                cnt = (dist[i]*2);
                ans++;
            } else {
                cnt += (dist[i]*2);
            }
            
        }
    }
    return ans;
}

int main() {
    int n,m,x,y,a,b,c; cin >> n >> m >> x >> y;

    for(int i=0; i<m; i++) {
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b,c));
        graph[b].push_back(make_pair(a,c));
    }
    cout << dijkstra(y,n,x);
}