[c++] 프로그래머스 - 배달( Level2)

문제

코딩테스트 연습 - 배달

 

코드

#include <iostream>
#include <vector>
#define INF 1e9

using namespace std;



int solution(int N, vector<vector<int> > road, int K) {
    int graph[51][51]={0, };
    int answer = 0;
    vector<int>memory_city_cnt;

    for(int i=0; i<N; i++){
        for(int k=0; k<N; k++){
            if(i==k) graph[i][k] = 0;
            else graph[i][k] = INF;
        }
    }

    for(int i=0; i<road.size(); i++){
        int a = road[i][0]-1;
        int b = road[i][1]-1;
        int cost = road [i][2];
        graph[a][b] = min(graph[a][b],cost);
        graph[b][a] = min(graph[b][a],cost);
    }

    for(int k=0; k<N; k++){
        for(int a=0; a<N; a++){
            for(int b=0; b<N; b++){
                graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b]);
            }
        }
    }

    for(int k=0; k<N; k++){
        if(graph[0][k]<=K) memory_city_cnt.push_back(k);
    }

    answer = memory_city_cnt.size();
    return answer;
}

 

풀이

일반적인 플로이드-와샬 알고리즘을 수행한 후 마지막에 문제의 조건에 맞게 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 출력하면 되는 문제입니다.

주의해야 할 점은 입력에서 아래의 사진과 같이 한 도로의 정보가 중복해서 주어지기 때문에 입력을 받을 때 최소 값으로 갱신해줘야 합니다.