많이나오는 그래프에서의 최단거리(요금) 문제이다.
그래프 최단거리 문제의 해결법으로는
1. 다익스트라
2. 플로이드 와샬
두가지가 있다고 한다.
문제 해결하다가 시간내에 풀지 못해서 다른 사람이 풀어놓은 답을 참고했다.
최단 경로 : 두 노드를 잇는 가장 짧은 경로를 찾는 문제
가중치 그래프에서 edge의 가중치 합이 가장 작은 경로를 찾는 것
다익스트라 알고리즘
특정한 하나의 node에서 다른모든 node로 가는 최단 경로를 구할 수 있다.
설명 참조
edge 길이를 고려하여 노드에 순위를 매기기 위해서 '우선순위' 큐를 사용하고 BFS를 이용한다.
위와 같은 그래프가 있다고 할때 1에서 부터 모든 node의 최단거리를 구하려고 할때 2,3,4 node까지의 최단거리는 우선 3,6,7 이다.
여기서 1번 node와 가장 가까운 2번 node에서 다시 최단거리를 갱신해보면
1번에서 3번까지의 최단거리는 1->2->3 번까지인 4로 1->3의 최단거리를 갱신할 수 있다.
이런식으로 계속 반복해서 모든 node까지의 최단거리를 구하는 것이다.
- 출발 node 설정
- 출발 node를 기준으로 각 node 까지의 최소 비용 저장
- 아직 방문하지 않은 node중에서 최소 비용의 node 선택
- 위에서 선택한 node를 거쳐 특정한 node로 가는 경우를 고려하여 최소 비용을 갱신
- 3~4번을 반복한다.
위에가 다익스트라 알고리즘의 과정!
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = []
heapq.heappush(queue, [distances[start], start])
while queue:
current_distance, current_node = heapq.heappop(queue)
if distances[current_node] < current_distance:
continue
for adjacent, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[adjacent]:
distances[adjacent] = distance
heapq.heappush(queue, [distance, adjacent])
print(distances)
return distances여기서 graph의 형태는 dictionary에 key값은 node value값은 또다른 dictionary key: 연결 node번호 value : 가격으로 받는다.
형태 {1: {4:10, 3:41, 5:24, 6:25, 2:{4:66, 3:22 } ---}
이런식이다!
따라서 문제의 input을 이중 딕셔너리 형식으로 바꿔주어야 한다. 위 함수의 return은 시작점을 기준으로 다른 모든 node까지의 최소 비용이다.
2가지 경우의수
1. 두명이 아예 따로 택시를 탈때
2. 두명이 같이가다가 내려서 따로타는경우
1번째 경우의수에서는
다익스트라로 구한 (s-> a까지의 결과) + (s-> b 까지의 결과) 이다.
2번째 경우는
둘이 함께 탑승하는 중간지점을 구해서
(s -> 중간지점) + (중간지점 + a) + (중간지점-> b) 를 구하면된다.
여기서 중간지점은 a이거나 b일수도 있다. !!
위에서 구한값들을 저장해놨다가 최소값을 return 해주면된다.
문제에서 node의 최대 개수가 200개이기때문에 중간지점을 모두 구해서 비교해본다!
def solution(n, s, a, b, fares):
answer = []
dic = {}
for i in range(n):
dic[i + 1] = {}
for j in fares:
dic[j[0]][j[1]] = j[2]
dic[j[1]][j[0]] = j[2]
candidate = dijkstra(dic, s)
print(candidate)
# 그냥 따로따로 출발지에서 출발하는 경우
answer.append(candidate[a] + candidate[b])
for i in range(1, n + 1):
if i == s:
continue
mid = i
# print(dic)
temp = dijkstra(dic, mid)
answer.append(candidate[mid] + temp[a] + temp[b])
# print(temp)
return min(answer)
어렵다!!
