2021 KAKO BLIND RECRUITMENT [합승 택시 요금] [C++]

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

---

문제요약

1.비용이 각각 다른 양방향 간선이 주어진다

2.A,B두사람이 동시에 출발하는 지점 S와 두사람의 목적지 a,b가 주어진다

3.택시를 같이 타고 가다가 한명이 내려 다른 택시를 타고 가는게 가능하다고 할때 가능한 택시비 총합의 최소비용을 출력

 

---

나의 풀이

 

이문제를 분기전과 분기후로 나누면 다음과 같이 요약된다

 

1. s에서 A,B가 같이 출발해서 분기점(k)까지 간다
2. 분기점(k)에서 A는 a까지 간다
3. 분기점(k)에서 B는 b까지 간다

합승택시 요금은 1의 요금 + 2의 요금 + 3의 요금이 된다

 

여기서 그러면 k에 따라 합승택시 요금이 바뀌게 되고 특정 k노드에서 최소 합승 택시 요금이 나오게 된다

 

모든 k에 대해서 시뮬레이션을 돌리는 방법도 생각했었지만

어차피 k가 정해지면 나머지는 최소한의 비용으로 목적지로 갈게 당연하므로 다익스트라를 이용하기로 했다.

---

풀이 방법

1.s,a,b에서 출발하여 모든 노드까지 갈수있는 최소비용을 배열 3개를 이용하여 저장

 (다익스트라 알고리즘을 이용하여 모든 정점까지 최소비용을 계산)

2.특정k에 대해서

  s[k] + a[k] + b[k] 가 최소 가 되는 cost를 출력

---

코드

	#include <bits/stdc++.h>
	#define INF 0x3f3f3ff
	using namespace std;
	vector<pair<int,int>> edge[201];
	int dist[201][3];
	void shortestPath(int start,int idx,int n){
	bool visit[201];
	int c=n-1;
	memset(visit,false,sizeof(visit));
	dist[start][idx]=0;
	int cur=start,mindist=INF;
	visit[cur]=true;
	while(c--){
	for(int i=0;i<edge[cur].size();i++){
	auto p = edge[cur][i];
	dist[p.first][idx]=min(dist[p.first][idx],p.second+dist[cur][idx]);
	}
	for(int i=1;i<=n;i++){
	if(!visit[i]){
	if(mindist>dist[i][idx]){
	mindist=dist[i][idx];
	cur=i;
	}
	}
	}
	visit[cur]=true;
	dist[cur][idx]=mindist;
	mindist=INF;
	}
	return ;
	}
	int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
	int answer = INF;
	for(int i=0;i<=n;i++){
	for(int j=0;j<3;j++){
	dist[i][j]=INF;
	}
	}
	for(int i=0;i<fares.size();i++){
	int from = fares[i][0];
	int to = fares[i][1];
	int cost = fares[i][2];
	edge[from].push_back({to,cost});
	edge[to].push_back({from,cost});
	}
	shortestPath(s,0,n);
	shortestPath(a,1,n);
	shortestPath(b,2,n);
	for(int i=1;i<=n;i++){
	answer = min(answer , dist[i][0]+dist[i][1]+dist[i][2]);
	}
	return answer;
	}

view raw .cpp hosted with ❤ by GitHub