합승 택시 요금

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

문제설명:

노드와 엣지가 주어지고 출발지는 같고 목적지가 두개이다. 이때 택시를 타는것처럼 중간까지 같이가는경우는 한번만 비용을 낸다고 할때 목적지까지 도달하는 최소금액을 구하여라.

 

소요시간:

15분

난이도3

 

코딩:

def solution(n, s, a, b, fares):
	#플로이드로 전구간 이동경로 구하기
	INF = int(1e9)
	graph = [[INF]* (n+1) for _ in range(n+1)]
	for i in range(n+1):
		graph[i][i] = 0
	
	for start,end,cost in fares:
		graph[start][end] = cost
		graph[end][start] = cost

	for k in range(1,n+1):
		for y in range(1,n+1):
			for x in range(1,n+1):
				if graph[y][x] >graph[y][k] +graph[k][x]:
					graph[y][x] = graph[y][k] +graph[k][x]

	#합승을 하지않고 각자 이동하는경우
	ans = [graph[s][a]+graph[s][b]]

	#출발과 도착지점을 제외한 다른곳을 경유하면서 들르는 경우들의 합집합
	for i in range(1,n+1):
		if i !=[s,a,b]:
			ans.append(graph[s][i]+graph[i][a]+graph[i][b])

	return min(ans)

먼저 이문제를 보고, 완전탐색이 아닌 방법이 있을까 생각을 해보았고, n의 개수가 크지 않았기 때문에, 완전탐색을 해야겠다고 생각했습니다. 또한 특정 지점부터 특정 지점까지만 가는것이 필요하다면 다익스트라 알고리즘이 더 빠르지만 모든경우의 수가 필요하기 때문에 플로이드 알고리즘을 사용했습니다.

그래서 플로이드로 모든구간에 대한 코스트를 구한다음, 경유하지않고 다른지점을 들리는경우를 추가 후,

s,a,b즉 출발지점과 도착지점이 아닌 다른지점을 경유하는 경우 경유하는곳까지 cost그리고 거기서부터 양 도착지에까지 가는데 드는 cost를 합쳐주어 더해준 뒤, 그들 중 제일 작은 값을 찾아주었습니다.

 

피드백 :

추가적으로 다익스트라(우선순위큐)의 경우시간복잡도가O(nlogn)이어서, 모든 중간 노드를 기준으로 다익스트라를 구성하면 O(n^3logn)이기 때문에 플로이드 워셜을 사용한 것인데, 다익스트라 3번으로 할수 있는 알고리즘이 있다하여 찾아보는중이다. 

(추후 추가예정)