[프로그래머스 lv2] 배달 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

1번 노드에서 각 노드까지의 거리를 구한 후, 거리가 K이하인 노드의 개수를 세는 문제이다.

 

그래프에서 노드끼리의 거리를 구하기 위해서는 다음 세가지 알고리즘을 사용할 수 있다.

1) 다익스트라

2) 벨만-포드

3) 플로이드 와샬 

 

입력값의 범위가 50 이하이므로 O(v^3)의 시간 복잡도가 가능하다.

구현이 간단한 플로이드 와샬을 통해 각 노드까지의 거리를 구해보자.

(참고: 최단거리구하기_플로이드 와샬(Floyd Warshall) 알고리즘)

 

dp[i][j]는 i에서 j까지의 최단 거리이므로, dp[1][j] 값이 K이하인 노드의 개수를 세고 리턴하면 정답이다.

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int solution(int N, vector<vector<int>> road, int K) {
    
    vector<vector<int>> dp(N+1, vector<int>(N+1, 1000000000));
    
    for (int i=1; i<=N; i++) dp[i][i] = 0;
    for (auto v : road) {
        int a = v[0], b = v[1], c = v[2];
        dp[a][b] = min(dp[a][b], c);
        dp[b][a] = min(dp[b][a], c);
    }
    
    //Floyd
    for (int k=1; k<=N; k++) {
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++)
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
        }
    }
    
    int cnt = 0;
    for (int i=1; i<=N; i++) 
        if (dp[1][i] <= K) cnt++;

    return cnt;
}