[프로그래머스] 합승 택시 요금 (2021 KAKAO Blind Recruitment)

문제 링크

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

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

 

풀이

알고리즘을 조금이나마 공부해본 입장에선 전형적인 문제였습니다.

 

1-a) 플로이드-워셜로 모든 정점 간의 거리를 구해줍니다.

1-b) 양방향 간선이므로 거리[x->y], 거리[y->x]가 같습니다. 따라서 다익스트라를 3번 돌려 각각 s, a, b에서 시작하는 다른 모든 정점까지의 거리를 구해줘도 됩니다. 

2) i = 1 ~ n 에 대해, min( 거리[s->i] + 거리[i->a] + 거리[i->b] )가 정답입니다.

 

정답 코드

#include <bits/stdc++.h>
#define INF 222'222'222
using namespace std;

int d[222][222];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
	for(int i=1; i<n+1; i++){
		for(int j=1; j<n+1; j++){
			if(i == j) continue;
			d[i][j] = INF;
		}
	}
	for(const auto &e: fares){
   		int u = e[0], v = e[1], c = e[2];
		d[u][v] = d[v][u] = c;
	}
	for(int k=1; k<n+1; k++){
		for(int i=1; i<n+1; i++){
			for(int j=1; j<n+1; j++){
				d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
			}
		}
	}

	int ans = INF;
	for(int i=1; i<n+1; i++){
		if(d[s][i] != INF && d[i][a] != INF && d[i][b] != INF){
			int val = d[s][i]+d[i][a]+d[i][b];
			ans = min(ans, val);
		}
	}
	
	return ans;
}