[Python/프로그래머스]합승택시요금_플로이드와샬

 

 

 

 

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

프로그래머스

 

🐾 20221022

 

 

 

 

 

플로이드 와샬 백준 문제 풀이 :

https://what-am-i.tistory.com/425

[Python/BOJ] 백준11404 플로이드_플로이드와샬

 

 

 

 

 

플로이드 와샬 문제다!!

3중 for문 이용 

 

 

 

 

1 . 미리 이차원 배열을 int(1e9)의 값으로 초기화 초기화해서 만들어준다. 

x에서 x로 가는 비용은 0이므로 0으로 설정해주고 

fares로 주어진 비용들을 이차원 배열에 저장해준다. 

 graph = [[int(1e9)]*(n+1) for _ in range(n+1)]
    for i in range(1,n+1) :
        graph[i][i] = 0
        
    for i,j,cost in fares :
        graph[i][j] = graph[j][i] = cost

 

 

 

 

2.  3중 for문을 이용해 모든 노드에서 모든 노드로 가는 최소의 비용을 구해준다. 

k를 건너서 지나가는 모든 경우를 원래 값과 비교해서 갱신해주면 된다. 

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

 

 

 

 

3.  마지막, 최소의 요금은 

S에서 T까지 함께 타고 갔고

T 에서 A까지의 합, T에서 B까지의 합을 구해 최소 값을 구해주면 된다. 

 for i in range(1,n+1) :
        answer = min(answer, graph[s][i] + graph[i][a] + graph[i][b])

 

 

 

 

여기서 주의점은 n,s,a,b가 이미 지정된 값이 있기 때문에 내부에서 사용하면 안된다!!

 

 

 

전체 코드 : 

def solution(n, s, a, b, fares):
    answer = int(1e9)
    graph = [[int(1e9)]*(n+1) for _ in range(n+1)]
    for i in range(1,n+1) :
        graph[i][i] = 0
        
    for i,j,cost in fares :
        graph[i][j] = graph[j][i] = cost
        
    for k in range(1,n+1) :
        for i in range(1,n+1) :
            for j in range(1,n+1) :
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
    
    for i in range(1,n+1) :
        answer = min(answer, graph[s][i] + graph[i][a] + graph[i][b]) 
    return answer