Coding Test/프로그래머스(Python)
[프로그래머스/Python] Level 3_합승 택시 요금
syunze
2024. 3. 20. 12:51
📌문제 유형
최단거리(플로이드 워셜)
📌문제
📌나의 문제풀이
def solution(n, s, a, b, fares):
INF = 10000000
answer = INF
maps = [[INF] * (n+1) for _ in range(n+1)]
for i in range(n+1):
for j in range(n+1):
if i == j:
maps[i][j] = 0
for node1, node2, fare in fares:
maps[node1][node2] = fare
maps[node2][node1] = fare
for k in range(n+1): # 거치는 점
for i in range(n+1): # 시작 점
for j in range(n+1): # 끝 점
maps[i][j] = min(maps[i][k] + maps[k][j],maps[i][j])
for t in range(n+1):
temp = maps[s][t] + maps[t][a] + maps[t][b]
answer = min(temp, answer)
return answer
📌다른사람의 문제풀이
- 다익스트라
import heapq
def solution(n, s, a, b, fares):
INF = 10000000
answer = INF
graph = [[] * (n + 1) for _ in range(n + 1)]
for f in fares:
node1, node2, fee = f
# node1 - > node2 가는 요금이 fee
graph[node1].append((node2, fee))
# node2 - > node1 가는 요금이 fee
graph[node2].append((node1, fee))
def dijkstra(s):
q = []
# 최단거리 테이블을 무한으로 초기화
distance = [INF] * (n + 1)
# 거리(금액), 노드번호 순서
heapq.heappush(q, (0, s))
# 시작노드로 가는 최단거리는 0
distance[s] = 0
while q:
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 노드면 무시
if distance[now] < dist:
continue
for g in graph[now]:
cost = dist + g[1]
if cost < distance[g[0]]:
distance[g[0]] = cost
heapq.heappush(q, (cost, g[0]))
return distance
distance_list = [[]] + [dijkstra(i) for i in range(1, n + 1)]
for i in range(1, n + 1):
answer = min(distance_list[s][i] + distance_list[i][a] + distance_list[i][b], answer)
return answer
📌리뷰
- 최단거리 작성할 때 DFS말고 플로이드워셜, 다익스트라 있음을 기억하기!!!!!
- 플로이드 워셜 초기값 INF, 동일 위치인 경우 0으로 수정하기
728x90