[프로그래머스] 합승 택시 요금

문제

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

알고리즘 접근 방법

[플로이드 와샬 알고리즘]
1. 모든 i,j 정점으로 최단 경로가 저장된 테이블을 완성한 후
2. s부터 i까지 최단 경로 (합승) + i부터 a까지 최단경로 + i부터 b까지 최단 경로
중에 가장 최소가 되는 비용을 도출한다.

풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

#define INF 20000000

int minCostArr[204][204];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {

    int answer = INF;
    
    // 배열 초기화
    fill(&minCostArr[0][0], &minCostArr[0][0] + 204 * 204, INF);
    
    // 그래프 초기화
    for(vector<int> v : fares)
    {
        minCostArr[v[0]][v[1]] = v[2];
        minCostArr[v[1]][v[0]] = v[2];
    }
    
    // 자기 자신~자기자신 = 0 
    for(int i=1; i<=n; i++)
    {
        minCostArr[i][i] = 0;
    }
    

    // 플로이드 알고리즘 
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if (minCostArr[i][j] > minCostArr[i][k] + minCostArr[k][j])
                    minCostArr[i][j] = minCostArr[i][k] + minCostArr[k][j];
            }
        }
    }
    

    // 답 도출 s~i + i~a + i~b 가 최소인 것
    for(int i=1; i<=n; i++)
    {        
        if (answer > minCostArr[s][i] + minCostArr[i][a] + minCostArr[i][b])
        {
            cout << "s : " << s << ", i : " << i << " a : " << a << " , b : " << b << '\n';
            answer = minCostArr[s][i] + minCostArr[i][a] + minCostArr[i][b];
            cout << minCostArr[s][i] << "+" << minCostArr[i][a] << "+" << minCostArr[i][b] << "=" << answer << '\n';

        }
    }
    
    return answer;
}

정리

• INF 값을 처음에 잘못 설정해서 쓰레기 값이 나왔었다. 주의 !!!
• fill로 배열 초기화 할때도 꼭 size * size 만큼 해주기.. !

💡 참고 포스팅

[C++로 풀이] 합승 택시 요금 (플로이드 와샬, 다익스트라)⭐⭐⭐