[2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금

sewonK·2022년 1월 19일
1

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/72413

이 문제는 (S ➡ (어느 정점) ➡ A) + (S ➡ (어느 정점) ➡ B) 의 최소값을 찾는 문제였다.
최단 경로를 구하는 대표적인 알고리즘이 다익스트라 알고리즘인데, 음이 아닌 가중치 그래프일 때 특정 정점에서 다른 모든 정점으로 가는 최단 거리를 구할 때 주로 사용한다.

다익스트라 알고리즘 설명) https://m.blog.naver.com/ndb796/221234424646

이 문제는 하나의 정점이 아닌, 각 정점 간 최단 경로를 구하는 문제이기 때문에 플로이드 와샬 알고리즘을 적용해야 한다.
플로이드 와샬은 거쳐가는 정점을 기준으로 최단 거리를 구하는 알고리즘이다. 시간복잡도는 N^3으로 다익스트라 알고리즘보다는 오래 걸리지만, 음의 가중치가 있을 때나 간선의 수가 많을 때 사용하기 적절하다.

플로이드 와샬 알고리즘 설명) https://blog.naver.com/ndb796/221234427842

<문제 풀이 방법>
1) 자기자신으로 가는 비용을 제외한 나머지 비용을 INF로 초기화
2) fares 배열을 통해 연결되어 있는 정점 간 비용을 갱신
3) floyd warshall 알고리즘을 통해 정점 간 최소 비용을 갱신
4) (S ➡ (어느 정점) ➡ A) + (S ➡ (어느 정점) ➡ B)의 최소 비용 찾기

INF = 100000*200*200

def graphInit(n):
    global graph 
    graph = [[INF for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(n + 1):
            if i == j:
                graph[i][j] = 0

def floyd(n):
    global graph
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

def solution(n, s, a, b, fares):
    answer = INF
    global graph 
    graphInit(n)
    for fare in fares:
        graph[fare[0]][fare[1]] = fare[2]
        graph[fare[1]][fare[0]] = fare[2]
    floyd(n)
    for i in range(1, n + 1):
        if answer > graph[s][i] + graph[i][a] + graph[i][b]:
            answer = graph[s][i] + graph[i][a] + graph[i][b]
    return answer

0개의 댓글