Programmers - 합승 택시 요금

---

title: Programmers - 합승 택시 요금
date: 2022-07-22
tags:

• Algorithm
• Graph
• Floyd-Warshall

---

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

문제 요약

동일한 위치에서 출발하여 각자 A,B로 택시를 타고 간다.
처음부터 따로 갈 수 있고, 중간까지만 합승하였다가 이후 각자 택시를 타고 가도 된다.
최저 택시 요금을 계산하여 return한다.

문제 풀이

Floyd-Warshall 알고리즘을 사용하면 매우 간단한 문제이나, 잘못 접근하여 긴 시간동안 삽질을 했다.


Dijkstra 알고리즘을 사용하여 시작 노드 S에서 모든 노드로 가는 비용과 경로를 확인한 후, 해당 경로들만 이용하였을 때 최저 택시 요금을 구할 수 있다고 판단하였다.
그러나 1번 테스트 케이스에서 반례가 바로 존재하였고, 이전에 구한 경로들을 이용한 풀이를 생각하였다.
이전에 구한 경로에 있는 M 노드까지는 합승하고, 이후 M에서 각 노드로 가는 것이 최적이라고 판단하였다.
하지만 동일하게 1번 테스크 케이스에서 동일한 반례가 존재하였고, 결국 모든 노드를 점검하여야 했다.
S에서 출발하여 M 노드까지 합승하는 모든 경우의 수를 점검하였다.
처음에는 효율성 테스트에서 많은 시간 초과가 발생하였고, 이를 최대한 개선하고자 하였다.
return하게 될 best 값, 그리고 현재 점검중인 경로의 현재 값을 계속하여 비교하여 현재 값이 best보다 클 때 바로 다음 노드를 점검하는 방식으로 반복 횟수를 줄였다.
하지만 성능을 개선하고자 하는 노력은 약간의 성능 개선을 이루었으나, 구조적 문제로 인하여 일부 검사는 통과하기 못하였다.
과거에 배운 Graph 알고리즘을 다시 한 번 확인하며 Floyd-Warshall 알고리즘을 기억해냈고, 이를 사용하였다.


SM, MA, M~B가 필요하다. Floyd-Warshall은 서로의 경로 정보를 이용하여 한 step씩 갱신하는 방식이므로 모든 노드를 점검해야 정확한 값을 구할 수 있다.
각 노드를 순회하며 노드 to 노드의 모든 최소값을 갱신한다.
그리고 M 노드까지 합승하는 모든 경우의 수를 확인하며 최소 비용을 구한다.


사실 처음에 모든 노드를 점검하는것이 편하다는 것은 알았으나, 이게 꺼려져 다른 풀이를 찾다가 삽질을 하였다.
문제에서 최대 노드의 개수는 200개로, n^3의 경우 8M이다.
그리 크지는 않으나, 노드의 개수가 많아질수록 loop가 기하급수적으로 커지기에 이러한 방식을 좋아하지 않는다.
O(n^2) 이하의 좋은 성능의 알고리즘을 구현하고 싶었으나, 결국 모두 실패하고 Floyd-Warshall 알고리즘을 이용하였다.

프로그램 using Floyd-Warshall

#include <vector>
#include <utility>
#include <algorithm>
#include <stdio.h>

using std :: vector ;
using std :: pair ;
using std :: make_pair ;
using std :: min ;

int solution ( int n , int s , int a , int b , vector < vector < int > > fares )
{
    int iAnswer = 2e7 ;
    vector < vector < int > > vMinimumLength ( n , vector < int > ( n , 2e7 ) ) ;    // [ i ] [ j ] : Minimum length of i to j
    int iFareSize = fares.size () ;



    for ( int i = 0 ; i < iFareSize ; ++i )
    {
        int * ipTemp = fares [ i ].data () ;
        int iTempStart = * ipTemp ++ - 1;
        int iTempEnd = * ipTemp ++ - 1 ;
        int iTempCost = * ipTemp ++ ;

        vMinimumLength [ iTempStart ] [ iTempEnd ] = iTempCost ;
        vMinimumLength [ iTempEnd ] [ iTempStart ] = iTempCost ;
    }
    for ( int i = 0 ; i < n ; ++i )
    {
        vMinimumLength [ i ] [ i ] = 0 ;        
    }

    for ( int k = 0 ; k < n ; ++k )
    {
        for ( int i = 0 ; i < n ; ++i )
        {
            for ( int j = 0 ; j < n ; ++j )
            {
                vMinimumLength [ i ] [ j ] = min ( vMinimumLength [ i ] [ j ] , vMinimumLength [ i ] [ k ] + vMinimumLength [ k ] [ j ] ) ;
            }
        }
    }
    for ( int i = 0 ; i < n ; ++i )
    {
        iAnswer = min ( iAnswer , vMinimumLength [ s - 1 ] [ i ] + vMinimumLength [ i ] [ a - 1 ] + vMinimumLength [ i ] [ b - 1 ] ) ;
    }


    return iAnswer ;
}

프로그램 using Dijkstra

#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define PII pair < int , int >

using std :: vector ;
using std :: pair ;
using std :: make_pair ;
using std :: priority_queue ;

struct pqPII
{
    int iTarget ;
    int iCost ;

    pqPII ( int iTarget , int iCost ) : iTarget ( iTarget ) , iCost ( iCost ) {}
} ;

struct comp
{
    bool operator () ( const pqPII & a , const pqPII & b )
    {
        return a.iCost > b.iCost ;
    }
} ;

vector < vector < PII > > vPath ;
int iTotalNode ;
int iCurrentAnswer ;
int iExpectAnswer ;

void updateMinimumLength ( int iStart , int iEnd )                            // Update iExpectAnswer
{
    priority_queue < pqPII , vector < pqPII > , comp > pqBFS ;                // Store the index to update
    vector < bool > vVisit ( iTotalNode + 1 , false ) ;
    vector < int > vMinimumLength ( iTotalNode + 1 , -1 ) ;



    vMinimumLength [ iStart ] = 0 ;
    pqBFS.emplace ( iStart , 0 ) ;

    while ( -1 == vMinimumLength [ iEnd ] )
    {
        while ( ( ! pqBFS.empty () ) && ( vVisit [ pqBFS.top ().iTarget ] ) )
        {
            pqBFS.pop () ;
        }
        if ( pqBFS.empty () || ( iCurrentAnswer < pqBFS.top ().iCost + iExpectAnswer ) )    // Can't reach to iEnd
        {
            iExpectAnswer = 2e7 ;
            return ;
        }

        int iTarget = pqBFS.top ().iTarget ;
        int iCost = pqBFS.top ().iCost ;
        pqBFS.pop () ;

        vVisit [ iTarget ] = true ;
        vMinimumLength [ iTarget ] = iCost ;
        int iGraphSize = vPath [ iTarget ].size () ;
        PII * pTemp = vPath [ iTarget ].data () ;

        for ( int i = 0 ; i < iGraphSize ; ++i )
        {
            PII tempPII = pTemp [ i ] ;
            if ( ! vVisit [ tempPII.first ] )
            {
                pqBFS.emplace ( tempPII.first , iCost + tempPII.second ) ;
            }
        }
    }

    iExpectAnswer += vMinimumLength [ iEnd ] ;
}

int solution ( int n , int s , int a , int b , vector < vector < int > > fares )
{
    iCurrentAnswer = 2e7 ;
    vPath.resize ( n + 1 ) ;            // [ Start ] < End , Cost >
    int iFareSize = fares.size () ;
    iTotalNode = n ;



    for ( int i = 0 ; i < iFareSize ; ++i )
    {
        int * ipTemp = fares [ i ].data () ;
        int iTempStart = * ipTemp ++ ;
        int iTempEnd = * ipTemp ++ ;
        int iTempCost = * ipTemp ++ ;

        vPath [ iTempStart ].emplace_back ( make_pair ( iTempEnd , iTempCost ) ) ;
        vPath [ iTempEnd ].emplace_back ( make_pair ( iTempStart , iTempCost ) ) ;
    }

    for ( int i = 1 ; i <= n ; ++i )
    {
        iExpectAnswer = 0 ;
        updateMinimumLength ( s , i ) ;
        updateMinimumLength ( i , a ) ;
        updateMinimumLength ( i , b ) ;

        iCurrentAnswer = std :: min ( iCurrentAnswer , iExpectAnswer ) ;
    }


    return iCurrentAnswer ;
}