[프로그래머스][level3] 합승 택시 요금 -python

문제 링크

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

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

풀이

• 다익스트라 알고리즘 사용 
• 다익스트라 알고리즘 이란 ?
  •  
  • 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 다익스트라 알고리즘에서 시작 노드와 끝노드를 설정해주어, 최단 경로를 구하도록 했는데 계속 틀린 답이 나왔다. 그 이유는 dijkstra 함수에 매개 변수로 넘긴 a와 b가 계속 다른 값으로 나타났다. 이 값은 for문에서 사용된 a,b의 마지막 값이었다... for문에 사용된 변수 이름을 a,b가 아닌 다른 이름으로 수정하니 바로 해결되었다... 이걸로 시간 많이 쏟음. 앞으로 변수명이 겹치지 않도록 주의 .. 

# 틀린 코드
INF = int(1e9)
import heapq

def solution(n, s, a, b, fares):

  graph = [ [] for _ in range(n+1) ]
  for a, b, c in fares:
    graph[a].append((b,c))
    graph[b].append((a,c))

  answer = INF

  for t in range(1, n+1):
    answer = min(answer, dijkstra(graph,n,s,t)+dijkstra(graph,n,t,b)+ dijkstra(graph,n,t,a))

  return answer
  
def dijkstra(graph, n, start, end):

  distance = [INF] * (n+1)
  q = []
  heapq.heappush(q, (0,start))
  distance[start] = 0
  while q :
    # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기 
    dist, now = heapq.heappop(q)
    # 이미 처리된 적이 있으면 무시 
    if distance[now] < dist :
      continue
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))

  return distance[end]

• 아래는 제출한 코드이다. 

• INF = int(1e9)
  import heapq
  
  def solution(n, s, a, b, fares):
  
    graph = [ [] for _ in range(n+1) ]
  
    # 거리 저장 
    for e1, e2, c in fares:
      graph[e1].append((e2,c))
      graph[e2].append((e1,c))
  
    answer = INF
  
    for t in range(1, n+1):
        # 최단 비용 거리 
      answer = min(answer, dijkstra(graph,n,s,t)+dijkstra(graph,n,t,b)+ dijkstra(graph,n,t,a))
      print(answer)
  
    return answer
    
  # 다익스트라 알고리즘 
  def dijkstra(graph, n, start, end):
  
    distance = [INF] * (n+1)
    q = []
    heapq.heappush(q, (0,start))
    distance[start] = 0
    while q :
      # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기 
      dist, now = heapq.heappop(q)
      # 이미 처리된 적이 있으면 무시 
      if distance[now] < dist :
        continue
      for i in graph[now]:
        cost = dist + i[1]
        if cost < distance[i[0]]:
          distance[i[0]] = cost
          heapq.heappush(q, (cost,i[0]))
  
    return distance[end]