[2023년 11월 24일]배달(23분)

https://school.programmers.co.kr/learn/courses/30/lessons/12978

구현 아이디어 6분 구현 17분

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 양수 간선, 사이클 존재. 우선순위 큐를 다익스트라에 활용.
int dist[51];
vector<pair<int, int>> graph[51];

struct Data
{
    int index, dist;
    Data(int index, int dist)
    {
        this->index = index;
        this->dist = dist;
    }
    bool operator<(const Data& b) const
    {
        return dist > b.dist;   // 최소힙.
    }
};

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;

    int M = road.size();
    
    for(int i = 0; i < M; ++i)
    {
        int a, b, c;
        a = road[i][0];
        b = road[i][1];
        c = road[i][2];
        
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    
    for(int i = 1; i <= N; ++i)
        dist[i] = 2147000000;
    
    dist[1] = 0;
    
    priority_queue<Data> pQ;
    pQ.push(Data(1, 0));
    
    while(!pQ.empty())
    {
        Data data = pQ.top();
        pQ.pop();
        
        for(int i = 0; i < graph[data.index].size(); ++i)
        {
            int check_index = graph[data.index][i].first;
            int check_dist = dist[data.index] + graph[data.index][i].second;
            if(check_dist < dist[check_index])
            {
                dist[check_index] = check_dist;
                pQ.push(Data(check_index, check_dist));
            }
        }
    }
    
    //for(auto it : dist)
        //printf("%d ", it);
    
    for(int i = 1; i <= N; ++i)
        if(dist[i] <= K) ++answer;
    
    return answer;
}

---

풀이(벨만-포드)

#include <iostream>
#include <vector>
using namespace std;

// 벨만-포드.
// 1~N-1개의 간선을 거치는 경우 계산.

int result[51];
struct Edge
{
    int e, dist;
    Edge(int e, int dist)
    {
        this->e = e;
        this->dist = dist;
    }
};

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;
    int M = road.size();
    
    for(int i = 1; i <= N; ++i)
        result[i] = 2147000000;
    result[1] = 0;
    
    vector<Edge> Ed[51];
    
    for(int i = 0; i < M; ++i)
    {
        int s, e, dist;
        s = road[i][0];
        e = road[i][1];
        dist = road[i][2];
        
        Ed[s].push_back(Edge(e, dist));
        Ed[e].push_back(Edge(s, dist));
    }
    
    // i개의 간선을 지나는 경우.
    for(int i = 1; i < N; ++i)
    {
        // 마을 인덱스.
        for(int j = 1; j <= N; ++j)
        {
            for(int k = 0; k < Ed[j].size(); ++k)
            {
                int e = Ed[j][k].e;
                if(result[j] == 2147000000) continue;
                if(result[j] + Ed[j][k].dist >= result[e]) continue;
                result[e] = result[j] + Ed[j][k].dist;
            }
        }
    }
    
    // 음의 사이클 확인.
    for(int j = 1; j <= N; ++j)
    {
        for(int k = 0; k < Ed[j].size(); ++k)
        {
            int e = Ed[j][k].e;
            if(result[j] == 2147000000) continue;
            if(result[j] + Ed[j][k].dist >= result[e]) continue;
            return -1;
        }
    }
    
    for(int i = 1; i <= N; ++i)
        if(result[i] <= K) ++answer;

    return answer;
}