[프로그래머스] 카카오기출 / 합승택시 / python

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

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

 

🤔문제접근

1. 플로이드-워셜 알고리즘으로 각 출발지 -> 도착지의 가장 최저 요금을 2차원행렬로 만들어준다.

2. 합승해서 타는 지점을 모두 체크하여(출발지를 합승지로 지정하면 합승 안하는 것 까지 체크 가능) 가장 적은 요금이 드는 경우의 수를 답으로 도출한다.

 

플로이드-워셜 알고리즘

• 모든 최단 경로를 구하는 알고리즘
• 노드 간의 최단 경로를 입려겨한 2차원 행렬을 구성한다.
• 경유지를 설정하고. 각 시행마다 새로운 경유지로 교체해가며,
  • 기존의 출발->도착 경로와 출발->new경유지->도착의 경로를 비교하여 더 짧은 경로를 선택한다.

n = 6
fares = [[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]]

# n : 노드의 수 
# fares : 출발, 도착, 요금의 정보가 주어진다고 했을 때

INF = 1e10   # 충분히 큰 수

# dist -> x에서 y로 가는 운임 나타내는 2차원 요금지도
dist = [[INF for _ in range(n)] for _ in range(n)]

# 나 자신 -> 나 자신으로 가는 경우 0으로 설정
for i in range(n):
    dist[i][i] = 0
    
# fares로 받은 운임 적용해주기
for info in fares:
    # 우린 인덱스를 0부터 쓰니깐 -1해주자
    dist[info[0]-1][info[1]-1] = info[2]
    # 양방향으로 적용
    dist[info[1]-1][info[0]-1] = info[2]

여기까지 적용하면 아래와 같은 2차원 요금지도 확인 가능

# 플로이드-워셜 알고리즘 적용
def floyd(dist, n):
    # i->j로 가는 최단거리를 저장하려고 하는거임
    # k라는 경유지를 두고 i에서 j로 갈때 i->k->j가 빠른지 현재의 i->j가 빠른지 비교
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

floyd(dist, n)

그럼 아래와 같은 모든 경로의 최단거리 알 수 있는 요금지도 완성

 

💥코드구현

INF = 1e10
def floyd(dist, n):
    # i->j로 가는 최단거리를 저장하려고 하는거임
    # k라는 경유지를 두고 i에서 j로 갈때 i->k->j가 빠른지 현재의 i->j가 빠른지 비교
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

def solution(n, s, a, b, fares):
    # dist -> x에서 y로 가는 운임 나타내는 2차원 요금지도
    dist = [[INF for _ in range(n)] for _ in range(n)]

    # 나 자신 -> 나 자신인 경우 0으로 설정
    for i in range(n):
        dist[i][i] = 0

    # fares로 받은 운임 적용해주기
    for info in fares:
        # 우린 인덱스를 0부터 쓰니깐 -1해주자
        dist[info[0] - 1][info[1] - 1] = info[2]
        # 양방향으로 적용
        dist[info[1] - 1][info[0] - 1] = info[2]

    # 플로이드워셜 알고리즘 이용해서 2차원 요금지도 완성
    floyd(dist, n)
    # for i in range(n):
    #     print(*dist[i])

    # s, a, b 역시 -1 해줘야 인덱스가 맞음
    s -= 1
    a -= 1
    b -= 1
    answer = INF
    # k라는 경유지까지 합승하고 그곳에서 갈라지는 경우의 수 모두 비교
    # k에는 출발지도 포함되므로 (dist[s][s]도 있다는 뜻)
    # 합승안하는 경우도 체크할 수 있음
    for k in range(n):
        answer = min(answer, dist[s][k] + dist[k][a] + dist[k][b])

    return answer