[프로그래머스/Lv3] 합승 택시 요금 - Python

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

프로그래머스

 

문제 조건

1. A의 이동경로 : s -> b, B의 이동경로 : s -> b

2. 두 사람의 경유지가 같을 경우 같은 택시를 타며, 요금은 한 번만 지불

3. 두 사람의 총 택시 요금의 최소값 출력

 

접근 방식

일단 A와 B의 공통 경유지를 생각하자마자 플로이드 워셜로 풀어야겠다고 생각했다.

 

플로이드 워셜 코드 구현

1. 그래프 초기화

dist = [[float('inf')] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    dist[i][i] = 0

for x, y, f in fares:
    dist[x][y] = f
    dist[y][x] = f

 

2. 플로이드 워셜 수행

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

3. 최소 요금 갱신

answer = float('inf')
for k in range(1, n + 1):
    answer = min(answer, dist[s][k] + dist[k][a] + dist[k][b])

 

 

이렇게 풀다보니 구현은 간단했는데, 플로이드 워셜의 시간복잡도가 O(n^3)이다 보니 너무 오래걸렸다.

n = 200이라 통과는 가능했지만, 효율성 테스트 시간이 너무 오래걸렸고 다익스트라로 다시 풀어봣다

 

 

다익스트라 코드 구현

1. 그래프 초기화

adjl = [[] for _ in range(n + 1)]

for x, y, f in fares:
    adjl[x].append((f, y))
    adjl[y].append((f, x))

 

2. s에서 출발하여 다른 노드들 사이의 최소거리 dijkstra 구현

from heapq import heappop, heappush

def dijkstra(s, n, adjl):
    dist = [float('inf')] * (n + 1)
    dist[s] = 0
    heap = [(0, s)]

    while heap:
        d, cur = heappop(heap)

        if d > dist[cur]:
            continue

        for nd, next in adjl[cur]:
            if dist[next] > nd + d:
                dist[next] = nd + d
                heappush(heap, (nd + d, next))

    return dist

 

3. dist_n : n에서 출발하여 다른 노드들 사이의 최소거리

dist_s = dijkstra(s, n, adjl)
dist_a = dijkstra(a, n, adjl)
dist_b = dijkstra(b, n, adjl)

 

 

4. 최소 요금 갱신

answer = float('inf')

for k in range(1, n + 1):
    answer = min(dist_s[k] + dist_a[k] + dist_b[k], answer)

 

 

 

최종 코드

1. 다익스트라

# 시간복잡도 : O(E log N)

from heapq import heappop, heappush

def dijkstra(s, n, adjl):
    dist = [float('inf')] * (n + 1)
    dist[s] = 0
    heap = [(0, s)]

    while heap:
        d, cur = heappop(heap)

        if d > dist[cur]:
            continue

        for nd, next in adjl[cur]:
            if dist[next] > nd + d:
                dist[next] = nd + d
                heappush(heap, (nd + d, next))

    return dist

def solution(n, s, a, b, fares):
    adjl = [[] for _ in range(n + 1)]

    for x, y, f in fares:
        adjl[x].append((f, y))
        adjl[y].append((f, x))

    dist_s = dijkstra(s, n, adjl)
    dist_a = dijkstra(a, n, adjl)
    dist_b = dijkstra(b, n, adjl)

    answer = float('inf')

    for k in range(1, n + 1):
        answer = min(dist_s[k] + dist_a[k] + dist_b[k], answer)

    return answer

 

2. 플로이드 워셜

# 시간복잡도 : O(N^3)

def solution(n, s, a, b, fares):
    dist = [[float('inf')] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        dist[i][i] = 0

    for x, y, f in fares:
        dist[x][y] = f
        dist[y][x] = f

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    answer = float('inf')
    for k in range(1, n + 1):
        answer = min(answer, dist[s][k] + dist[k][a] + dist[k][b])

    return answer