프로그래머스 - 배달 [C++]

이 문제는 최단 경로 알고리즘을 사용해서 풀었다.

 

집의 개수가 최대 50개이고, 1번 집부터 모든 각 집까지의 비용이 K 이하인 모든 집을 찾는 문제이다.

 

플로이드 워셜 알고리즘은 O(N^3) 이므로, 50^3 = 125,000 이므로 1초 내에 충분히 풀 수 있다.

 

한 가지 유의할 점은 같은 집 쌍에 대해 여러 도로가 존재할 수 있다는 것이다. 이 경우 여러 도로 중 가장 cost가 작은 도로를 해당 집 쌍의 비용으로 정하면 쉽게 풀 수 있다.

 

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

#define HOUSE_MAX 50
#define INF 1000000000

int dist[HOUSE_MAX + 1][HOUSE_MAX + 1];

void floydWarshall(int N) {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (dist[i][j] >= dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

void init(int N) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) {
                dist[i][j] = 0;
                
                continue;
            }
            dist[i][j] = INF;
        }
    }
}

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

    init(N);
    
    for (vector<int> info : road) {
        int src = info[0];
        int dst = info[1];
        int cost = info[2];
        
        int resultCost = min(dist[src][dst], cost);
        
        dist[src][dst] = resultCost;
        dist[dst][src] = resultCost;
    }
    
    floydWarshall(N);
    
    for (int i = 1; i <= N; i++) {
        if (dist[1][i] <= K) {
            answer++;
        }
    }

    return answer;
}