[Python] 합승 택시 요금

1. 문제

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

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

 

2. 풀이

• 이상한 부분으로 한참을 헤맸던 문제
• 풀고나니 생각보다 간단해서.,. 실력이 언제 늘라나.. 싶었음..
• 플루이드 워셜 알고리즘을 사용하여 풀었다

플루이드 워셜

플루이드 워셜 알고리즘?

A -> B로 이동한다 했을 때, A->1->B, A->2->B ... , A->N->B 로 모든 정점을 중간 노드라고 가정했을때의 최소값을 찾는다. 그게 A->B 의 최소값으로 업데이트

A->C 로 이동한다고 했을 때, A->1->C, ..., A->B->C 를 계산할 때 아까 구한 A->B의 최소값을 이용하여 구한다.

이런식으로 최소값 하나를 구하면 계속 그걸 이용해서 다른 최소값을 구하는 알고리즘

• 근데 여기서 for문 순서에 있어서 Nextnode가 맨위에 있지 않으면 오답이다. (i,j 순서는 상관없음)
  • 내가 고찰한(?) 이유
  1. 중간 노드 별 i->j 의 최소값이 계속 업데이트가 되어야 함
  2. 이전의 i->j의 최소값이 정해지지 않은 상태에서 중간노드가 바뀌면, 다음의 i->j 가 최소인지를 확신할 수 없음

 

3. 코드

maxnum = 200000001
def solution(n, s, a, b, fares):
    s,a,b = s-1,a-1,b-1 
    
    # 거리 리스트 초기화
    dist = []
    for i in range(n) : 
        dist.append([maxnum]*n)
    for i in range(n) : 
        dist[i][i] = 0
    for p1,p2,d in fares:
        dist[p1-1][p2-1] = d
        dist[p2-1][p1-1] = d
    
    # 최소 거리로 업뎃
    for nextnode in range(n):
        for j in range(n):
            for i in range(n):
                if i==j : continue
                if dist[i][nextnode] != maxnum and dist[nextnode][j] != maxnum:
                        dist[i][j] = min(dist[i][j], dist[i][nextnode] + dist[nextnode][j])
                        dist[j][i] = dist[i][j] 

    # 최소값 찾기
    answer = maxnum
    for h in range(n):
        answer = min(answer, dist[s][h] + dist[h][a] + dist[h][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]])