[프로그래머스] 파이썬 문제풀이 - 합승 택시 요금

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

프로그래머스

이 문제를 보면 그래프 문제라는것과 정점 사이의 최단거리를 구해야한다는 것을 파악해야한다. 그렇다면 모든 정점에서 모든 정점으로의 최단 경로를 구할 수 있는 플로이드 와샬 알고리즘을 적용해볼 수 있다. 하지만 여기서 합승이라는 개념이 조금 어렵게 다가올 수 있다.

 

출발지를 S

사람 a의 목적지를 A

사람 b의 목적지를 B
마지막으로 합승에서 하차하는 지점을 C라고 생각해보자

 

우리의 목적은 S ~ C 구간 , C ~ A 구간, C ~ B 구간 의 합이 최소화 되는 값을 찾는 것이다. 이 과정에서 우리는 마지막으로 하차하는 지점인 c를 특정하기 힘드므로 1~N까지의 모든 지점을 하차지점으로 생각해서 구해보면 된다.

내 풀이

1. n*n 크기의 2차원 리스트 만들기

2. 자기에서 자신으로 가는 비용 0으로 초기화

3. 간선 정보를 리스트에 입력해준다. 쌍방향이므로 양쪽 다 입력해야한다

4. 플로이드 와샬 알고리즘에 핵심인 3중 for문을 통해 정점에서 정점을 이동할 때 최단거리를 구한다

5. 우리는 합승을 하고 하차해서 각자 가는 지점을 모르기에 for문을 통해 돌려본다

def solution(n, s, a, b, fares):
    maps=[[1000001]*n for _ in range(n)]
    for i in range(n):
        maps[i][i]=0
        
    for i in fares:
        x,y,z=i[0]-1,i[1]-1,i[2]
        maps[x][y]=z
        maps[y][x]=z
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if maps[j][i]+maps[i][k]<maps[j][k]:
                    maps[j][k]=maps[j][i]+maps[i][k]
  
    return min(maps[s-1][i]+maps[i][a-1]+maps[i][b-1] for i in range(n))

배운 점

1. 변수가 중복됐는지 확인할 것, 변수가 중복된걸 모르고 한참을 헤맸다 알고보니 단순한 변수중복문제였다...

2. 모든 정점에서 모든 정점으로의 최단 경로를 구해야 할 때는 플로이드 와샬 알고리즘을 적용해볼 수 있다