[PRO] 2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금 (Python/플로이드워셜)

🌱 발상 🌱

1️⃣ 최단 거리 문제 → 다익스트라로 풀까? 하다가 플로이드-워셜로 변경

• 처음엔 다익스트라로 S→A, S→B 를 구하고, S→A를 가는 길들을 0으로 초기화하면서 S→B를 구해볼까 했는데 어디까지 동행할지 정하는 과정이 복잡해서 포기
• 굳이 S→A, S→B만 구할 이유가 있나? 결국 S→같이타는마지막노드(D) + D→A + D→B 라고 생각했고 이 D는 모든 노드가 될 수 있을 것이라는 생각이 들었음. ⇒ 이럴거면 플로이드-워셜로 다 구해서 쓰자
  

🪴 풀이 🪴

👩🏻‍💻 코드

def solution(n, s, a, b, fares):
    INF = 1e8
    graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j:
                graph[i][j] = 0
    
    for fare in fares:
        i, j, w = fare
        graph[i][j] = w
        graph[j][i] = w
    
    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])
    
    answer = INF
    for k in range(1, n+1):
        answer = min(answer, graph[s][k] + graph[k][a] + graph[k][b])

    return answer

1️⃣ 변수 선언 & 초기화

• INF: 무한대
• graph: 한 노드에서 다른 노드까지 가는 최소 비용을 담은 2차원 배열
  • 각 노드 번호가 1부터 시작하므로 n+1 x n+1 의 크기 선언해 사용이 편하도록 함
  • 처음엔 모든 노드에 대하여 무한대로 초기화
  • 자기 자신에서 자기 자신으로 가는 경우(1→1, 3→3)는 0으로 초기화
  • 비용 정보로 초기화(fares 를 for 문으로 돌면서 i → j, j → i 를 모두 w 로 초기화함)

2️⃣ 플로이드 워셜

• 각 노드를 i에서 j로 가는 최소 비용을 모든 정점을 거쳐간다고 가정하면서 초기화

3️⃣ 가장 적은 비용이 발생하는 경유 노드 탐색

• 모든 정점에 대해 반복문을 돌면서 가장 적은 비용이 발생하는 경우를 answer 에 대입

---

🌻 후기 🌻

🤔 생각해볼 점

없음

🆕 새롭게 알게 된 점

없음

🏛️삽질기

없음