[2021 카카오 블라인드 테스트] 합승 택시 요금
0. 처음에 작성한 코드
from collections import deque
def dikstara(s, n, edge):
visited = [False for _ in range(n+1)] # 해당 지점을 방문했는가
maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
dist = [maxDist for _ in range(n+1)] # 해당 지점에 대한 최소 요금
q = deque([(s, 0)])
dist[s] = 0
while q:
v = q.popleft()
x = v[0]
# 재방문해도 더 빠를 수 있고, 재방문하면 안된다는 조건은 없으니 해당 코드는 삭제한다.
# if visited[x] == True:
# continue
# visited[x] = True
for k in edge[x]:
if dist[k[0]] > dist[x] + k[1]: # 현재 저장된 k에 가는데 드는 비용 > x에 가는데 드는 비용 + x에서 k로 가는데 드는 비용
dist[k[0]] = dist[x] + k[1]
q.append((k[0], dist[k[0]]))
return dist
def solution(n, s, a, b, fares):
answer = 0
edge = [[] for _ in range(n+1)] # 간선별 요금 정보 저장 edge[출발지점] = [(도착지점, 요금)]
maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
for fare in fares:
edge[fare[0]].append((fare[1], fare[2]))
edge[fare[1]].append((fare[0], fare[2]))
startDist = dikstara(s, n, edge)
answer = startDist[a] + startDist[b] # (S -> A) + (S -> B) 합승하지 않는 경우
for i in range(1, n+1):
if i != s and startDist[i] < maxDist:
nDist = dikstara(i, n, edge) # 합승 -> A, B 최단 경로 요금 / 어떤 특정 지점을 시작 지점이라고 보고 다시 최단 경로를 찾는다.
if answer > startDist[i] + nDist[a] + nDist[b]:
answer = startDist[i] + nDist[a] + nDist[b]
return answer
solution(6, 4, 6, 2, [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]])
재방문 처리하는 코드를 삭제 했더니 어찌어찌 통과가 됐다. 그런데 다른 사람들의 풀이를 보니 다익스트라에 대해 완전히 잘못 알고 있었고, 플로이드 워셜이라는 알고리즘에 대해 알게 되었다.
두 알고리즘을 비교해보려 한다.
1. 다익스트라 알고리즘
- 시작 지점에서 모든 노드까지의 최단 경로를 구한다.
- 우선순위 큐(힙큐)를 이용하여 현재 방문하지 않는 노드(내가 잘못 알고 있었던 부분)들 중에서 이동하는데 드는 비용이 적은 노드들부터 방문하여 처리한다.
- 음의 비용이 존재하면 사용할 수 없다. (시작 지점에서 모든 노드까지의 최단 경로를 구해야하는데, 음의 비용이 존재한다면 벨만 포드 알고리즘을 사용한다.)
import heapq
def dijkstra(s, n, edge):
visited = [False for _ in range(n+1)] # 해당 지점을 방문했는가
maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
dist = [maxDist for _ in range(n+1)] # 해당 지점에 대한 최소 요금
q = []
heapq.heappush(q, (0, s))
dist[s] = 0
while q:
v = heapq.heappop(q)
x = v[1]
if visited[x] == True:
continue
visited[x] = True
for k in edge[x]:
if dist[k[0]] > dist[x] + k[1]: # 현재 저장된 k에 가는데 드는 비용 > x에 가는데 드는 비용 + x에서 k로 가는데 드는 비용
dist[k[0]] = dist[x] + k[1]
heapq.heappush(q, (dist[k[0]], k[0]))
return dist
def solution(n, s, a, b, fares):
answer = 0
edge = [[] for _ in range(n+1)] # 간선별 요금 정보 저장 edge[출발지점] = [(도착지점, 요금)]
maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
for fare in fares:
edge[fare[0]].append((fare[1], fare[2]))
edge[fare[1]].append((fare[0], fare[2]))
startDist = dijkstra(s, n, edge)
answer = startDist[a] + startDist[b] # (S -> A) + (S -> B) 합승하지 않는 경우
for i in range(1, n+1):
if i != s and startDist[i] < maxDist:
nDist = dijkstra(i, n, edge) # 합승 -> A, B 최단 경로 요금 / 어떤 특정 지점을 시작 지점이라고 보고 다시 최단 경로를 찾는다.
if answer > startDist[i] + nDist[a] + nDist[b]:
answer = startDist[i] + nDist[a] + nDist[b]
return answer
2. 플로이드 워셜 알고리즘
- 모든 노드에서 다른 모든 노드까지의 최단 경로를 구한다.
- 방문하지 않은 노드들 중에서 최소 비용을 갖는 노드를 찾을 필요가 없다. (다익스트라와의 차이점)
- 점화식: D(ab) = min( D(ab), D(ak)+ D(kb)) --> a에서 바로 b로 이동하는 거리와, a에서 k를 거쳐 b로 이동하는 거리중에 짧은 것을 택한다.
- 보통 노드의 개수가 500개 이하이다.
- 음의 비용이 존재해도 사용할 수 있다.
def solution(n, s, a, b, fares):
answer = 0
maxDist = 20000000 # 200(최대 지점 갯수) * 100000(최대 요금)
dist = [[maxDist for _ in range(n+1)] for _ in range(n+1)] # dist[i][j] i에서 j까지 이동하는데 최소 비용
for fare in fares:
dist[fare[0]][fare[1]] = fare[2]
dist[fare[1]][fare[0]] = fare[2]
for i in range(1, n+1):
dist[i][i] = 0
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
answer = 40000000 # 원래 maxDist * 방문해야 하는 지점이 2개
for k in range(1, n+1):
if answer > dist[s][k] + dist[k][a] + dist[k][b]:
answer = dist[s][k] + dist[k][a] + dist[k][b]
return answer
Author And Source
이 문제에 관하여([2021 카카오 블라인드 테스트] 합승 택시 요금), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minjyo8823/2021-카카오-블라인드-테스트-순위-검색-qamwmnz4저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)