[프로그래머스] 배달

풀이)

1번 마을에서 다른 마을까지 가는 최소 거리를 구해놓고, 그 거리가 K이하면 배달이 가능한 지역이라고 보면 된다.

따라서 최소거리 알고리즘 중 플로이드 알고리즘을 사용해서 풀었다.

그러나, 굳이 플로이드로 구할 필요가 없다. 플로이드는 모든 마을에서 ~ 본인 마을을 제외한 모든 마을의 최소거리를 구하는 방식이다. 

이 문제에서는 1번 마을에서 다른 마을까지의 거리를 구하는 것이니깐 다익스트라 알고리즘을 사용해 1번 마을을 기준으로 구하는 방법이 시간적인 면에서 더 이득일 것이다.

주의할점

양방향 도로

코드)

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

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

    vector<vector<int>> adj(N+1,vector<int>(N+1,INF));
    for(int i=1;i<=N;i++){
        adj[i][i] = 0;//자기자신은 0
    }
    for(int i=0;i<road.size();i++){//양방향
        if(adj[road[i][0]][road[i][1]] > road[i][2]){
            adj[road[i][0]][road[i][1]] = road[i][2];
        }
        if(adj[road[i][1]][road[i][0]] > road[i][2]){
            adj[road[i][1]][road[i][0]] = road[i][2];
        }
    }
    //floyd
    for(int k=1;k<=N;k++){
        for(int i=1;i<=N;i++){
            if(adj[i][k] == INF) continue;
            for(int j=1;j<=N;j++){
                adj[i][j] = min(adj[i][j],adj[i][k] + adj[k][j]);
            }
        }
    }
    for(int i=1;i<=N;i++){
        if(adj[1][i] <= K)answer++;
    }
    return answer;
}