[프로그래머스]Lv3. 합승 택시요금(Python)

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

프로그래머스

 

문제 접근

 

특정 도시 간의 최소 요금을 계산하는 문제

특정 도시 간이므로 플로이드 와샬을 사용하는 건 기억이 났는데 코드를 기억에서 지워버렸나보다.. 반복문이 3겹이었던 기억이 난다.

스스로를 반성하게되는 모먼트.. 알고리즘을 복습하고 다시 접근..!!

 

알고리즘의 적용과 생각의 흐름

1. 무한대의 값으로 그래프를 초기화

2. 그래프의 대각선 요소는 자기 자신으로 가는 요금이므로 당연하게 0으로 초기화

3. fares에 담긴 요금 정보를 바탕으로 그래프 업데이트

4. (핵심1)플로이드 와샬 알고리즘을 사용해 모든 도시 간의 최소 요금의 값을 계산 => 껍데기는 거쳐가는 걸 기준!!

5. (핵심2) 출발지에서 각 도착지까지의 최소 요금을 계산하고, A와 B도시를 각각 경유하는 경우의 요금을 고려해  최소 요금을 갱신

 

코드

def solution(n, s, a, b, fares):
    INF = 10000000
    answer = INF
    graph = [[INF] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                graph[i][j] = 0

    for fare in fares:
        c, d, f = fare	# c ~ d까지 f원(양뱡향 연결)
        graph[c - 1][d - 1] = f
        graph[d - 1][c - 1] = f

    # 플로이드 와샬 알고리즘(모든 도시 간의 최소 요금)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

    
    for t in range(n):
        # s에서 t까지의 요금과 t를 경유해 A도시(a-1)와 B도시(b-1)로 가는 요금을 더한 값을 temp에 저장 
        temp = graph[s - 1][t] + graph[t][a - 1] + graph[t][b - 1]
        # 첫 번째 반복에서는 초기값이 INF이므로 temp 값으로 설정된 후 계속 최소 요금을 갱신  
        answer = min(temp, answer)

    return answer

 

문제 회고

 

왜 이태껏 알고리즘을 공부했는지 확인하는 문제.. 이런 문제가 나오면 꼭 맞고 들어가자..!!