프로그래머스 - 합승 택시 요금 (Lv.3)
문제 링크
- 👉 합승 택시 요금
문제 설명
- N개의 정점이 있고, 각 정점은 서로 가중치를 가진 간선으로 연결된 그래프 형태를 취하고 있다.
- 출발지점(S)와 두 사람의 목적지(A,B)가 주어진다.
- 두 사람이 서로의 목적지에 가는 방법은 다음과 같다.
- 합승을 통해 중간 지점까지 같이 이동한다.
- 중간 지점에서 서로의 목적지로 각자 이동한다.
- 합승을 하지 않고 처음부터 각자 이동할 수 있다.
문제 접근1
- 다익스트라 알고리즘
- 음의 가중치가 없는 그래프의 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
- 합승해서 갈 수 있는 모든 경로를 DFS 를 이용해 구한다.
- 합승을 통해 이동한 중간 지점에서 다익스트라 알고리즘으로 서로의 목적지까지 가는 최소 비용을 계산한다.
- 위와 같은 방식으로 완전 탐색을 하고, 최소가 되는 값을 반환한다.
구현(정확성 All Pass, 효율성 All Fail)
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <memory.h>
#include <algorithm>
#define INF 9e8
using namespace std;
// w = table[u].first, v = table[u].second
vector<pair<int, int>> table[201];
int cand[201][201]; // cand[v][u] 는 v가 u에서 왔을 때 비용
int answer = INF;
int N, A, B;
int cost[201];
bool visited[201];
void dijkstra(int start, int curCost){
for(int i=0; i<=N; i++){
cost[i]=INF;
}
cost[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, start));
while(!pq.empty()){
int u = pq.top().second;
int w = pq.top().first;
pq.pop();
for(int i=0; i<table[u].size(); i++){
int v = table[u][i].second;
int x = table[u][i].first;
if(w+x < cost[v]){
cost[v] = w+x;
pq.push(make_pair(w+x, v));
}
}
}
// 합승지점까지의 비용 + (A, B 지점까지의 비용)
int totalCost = curCost + cost[A] + cost[B];
answer = min(answer, totalCost);
// printf("%d -> %d(a) : %d\n", start, A, cost[A]);
// printf("%d -> %d(b) : %d\n", start, B, cost[B]);
// printf("current cost: %d\n", curCost);
// printf("total cost: %d\n",answer);
}
void taxiProcess(int u, int weight){
for(int i=0; i<table[u].size(); i++){
int v = table[u][i].second;
int w = table[u][i].first;
if(visited[v]) continue;
visited[v] = true;
dijkstra(v, weight+w);
taxiProcess(v, weight+w);
visited[v] = false;
}
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
N = n; A = a; B = b;
for(int i=0; i<fares.size(); i++){
int u = fares[i][0];
int v = fares[i][1];
int w = fares[i][2];
table[u].push_back(make_pair(w, v));
table[v].push_back(make_pair(w, u));
}
memset(visited, false, sizeof(visited));
dijkstra(s, 0); // 합승하지 않는 경우
taxiProcess(s, 0);
return answer;
}
문제 접근 2
- 다익스트라 알고리즘을 아래와 같이 적용한다.
- (
start -> mid까지 비용) + (mid->a까지 비용) + (mid->b까지 비용) 을 구해서 최솟값을 찾는다.
- (
구현(효율성 7,8번 Fail)
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#define INF 1000000
using namespace std;
// w = table[u].first, v = table[u].second
int N;
vector<pair<int, int>> table[201];
int cost[201];
int dijkstra(int start, int target){
for(int i=1; i<=N; i++){
cost[i]=INF;
}
cost[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
while(!pq.empty()){
int u = pq.top().second;
int w = pq.top().first;
pq.pop();
if(cost[u] < w) continue;
for(int i=0; i<table[u].size(); i++){
int v = table[u][i].second;
int x = table[u][i].first;
if(w+x < cost[v]){
cost[v] = w+x;
pq.push(make_pair(w+x, v));
}
}
}
return cost[target];
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int ret = INF;
N = n;
for(int i=0; i<fares.size(); i++){
int u = fares[i][0];
int v = fares[i][1];
int w = fares[i][2];
table[u].push_back(make_pair(w, v));
table[v].push_back(make_pair(w, u));
}
// 합승하지 않는 경우
ret = dijkstra(s, a) + dijkstra(s,b);
for(int i=1; i<=n; i++){
if(s!=i)
ret = min(ret, dijkstra(s,i) + dijkstra(i, a) + dijkstra(i, b));
}
return ret;
}
보완 내용
- 2번째 풀이는 다익스트라 알고리즘을 총
3xN + 2번 해야한다. - 다익스트라 알고리즘을 시작점 s에서 모든 점에 대해서 1번, a에서 모든 점에 대해서 1번, b에서 모든 점에 대해서 1번으로 총 3번만 진행할 수 있다.
- 2차원 배열의 형태로 0행은 시작점 s에서 모든 노드로 가는 최소비용을 담는다.
- 1행은 a에서 모든 노드로 가는 최소비용을 담는다.
- 2행은 b에서 모든 노드로 가는 최소비용을 담는다.
- 무방향 그래프이므로 출발지와 도착지의 관계는 중요하지 않기 때문에 가능한 풀이이다.
- 방향 그래프였다면 2차원 배열에 담긴 의미가 달라진다. 즉, s에서 1번 노드로 가는 최소비용과 1번 노드에서 s로 가는 최소비용은 달라질 수 있다.
- 방향 그래프일 때 이런 방법을 사용할 수 없는 이유는 시작점->중간점 은 배열의 정의대로 가지만, 중간점->A 혹은 B로 가는 경로는 출발점이 중간점이기 때문이다.
구현(All Pass)
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#define INF 1000000
using namespace std;
// w = table[u].first, v = table[u].second
int N;
vector<pair<int, int>> table[201];
int cost[201];
// s(0), a(1), b(2)
// dList[0][1]~dList[0][200] 은 s부터 각 노드까지의 최소비용
int dList[3][201];
void dijkstra(int idx, int start){
for(int i=1; i<=N; i++){
dList[idx][i]=INF;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
dList[idx][start]=0;
while(!pq.empty()){
int u = pq.top().second;
int w = pq.top().first;
pq.pop();
if(dList[idx][u] < w) continue;
for(int i=0; i<table[u].size(); i++){
int v = table[u][i].second;
int x = table[u][i].first;
if(w+x < dList[idx][v]){
dList[idx][v] = w+x;
pq.push(make_pair(w+x, v));
}
}
}
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
int ret = INF;
N = n;
for(int i=0; i<fares.size(); i++){
int u = fares[i][0];
int v = fares[i][1];
int w = fares[i][2];
table[u].push_back(make_pair(w, v));
table[v].push_back(make_pair(w, u));
}
dijkstra(0, s);
dijkstra(1, a);
dijkstra(2, b);
ret = dList[1][s] + dList[2][s];
for(int i=1; i<=n; i++){
if(dList[0][i]==INF || dList[1][i]==INF || dList[2][i]==INF) continue;
ret = min(ret, dList[0][i] + dList[1][i] + dList[2][i]);
}
return ret;
}
Leave a comment