프로그래머스 Lv2 배달

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

프로그래머스

나는 1번 마을에서 K시간 이하로 배달 할 수 있는 마을의 개수를 구하면 된다 이해했다.

최솟값을 구하기 위해 그래프와 각 마을의 도착 시간을 987654321으로 초기화했다.

    roads = vector<vector<int>>(N + 1, vector<int>(N + 1, 987654321));
    dp = vector<int>(N + 1, 987654321);

 

입력으로 들어온 road에서 시작점 도착점 시간을 가져와 최소시간으로 만들었다.

    for(int i = 0; i < road.size(); ++i)
    {
        int r = road[i][0];
        int c = road[i][1];
        int cost = road[i][2];
        
        roads[r][c] = min(roads[r][c], cost);
        roads[c][r] = min(roads[c][r], cost);
    }

그 다음 1번 마을의 시간을 0으로 초기화 한뒤 

1번 마을과 연결 된 마을을 탐색하면서 다음시간을 구하고, 정점의 시간보다 작다면 정점을 다음 시간으로 만들었다.

void dijkstra(int N)
{
    dp[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
    pq.push({0, 1});
    
    while(!pq.empty())
    {
        int time = pq.top().first;
        int current = pq.top().second;
        pq.pop();
        
        for(int i = 1; i <= N; ++i)
        {
            if(roads[current][i] != 987654321)
            {
                int nexttime = time + roads[current][i];
                int next = i;
                
                if(nexttime < dp[next])
                {
                    dp[next] = nexttime;
                    pq.push({nexttime, next});
                }
            }
        }
    }
}

roads[current[i] != 987654321을 체크하는 부분이 현재 마을에서 다음 마을이 연결되어있는지 확인하는 부분이다.

 

전체 코드는 아래와 같다.

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

vector<vector<int>> roads;
vector<int> dp;

void dijkstra(int N)
{
    dp[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
    pq.push({0, 1});
    
    while(!pq.empty())
    {
        int time = pq.top().first;
        int current = pq.top().second;
        pq.pop();
        
        for(int i = 1; i <= N; ++i)
        {
            if(roads[current][i] != 987654321)
            {
                int nexttime = time + roads[current][i];
                int next = i;
                
                if(nexttime < dp[next])
                {
                    dp[next] = nexttime;
                    pq.push({nexttime, next});
                }
            }
        }
    }
}

int solution(int N, vector<vector<int>> road, int K) {
    int answer = 0;
    roads = vector<vector<int>>(N + 1, vector<int>(N + 1, 987654321));
    dp = vector<int>(N + 1, 987654321);
    
    for(int i = 0; i < road.size(); ++i)
    {
        int r = road[i][0];
        int c = road[i][1];
        int cost = road[i][2];
        
        roads[r][c] = min(roads[r][c], cost);
        roads[c][r] = min(roads[c][r], cost);
    }
    dijkstra(N);
    
    for(int i = 1; i <= N; ++i)
    {
        if(dp[i] <= K)
            ++answer;
    }
    
    return answer;
}