문제 풀이/프로그래머스
프로그래머스 - 배달 [C++]
JJJaewon
2024. 1. 8. 20:56
반응형
이 문제는 최단 경로 알고리즘을 사용해서 풀었다.
집의 개수가 최대 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;
}
반응형