2021 KAKAO BLIND RECRUITMENT--합승 택시 요금 --C++

합승 택시 요금 바로가기
이 문제는 난이도가 굉장히 쉬웠다.
고민도 10분정도 밖에 안하고, 푸는데도 20분정도 밖에 안걸린문제..!!
딱 한번 제출하고 바로 맞췄는데 이 문제를 통해 굉장한 자신감을 얻었다.

일단 이 문제는 플로이드 와샬알고리즘을 쓰면된다.
물론, 다익스트라를 모든 노드에 적용하면 되지만,,, 굳이? 싶고 플로이드 와샬 알고리즘을 사용하면된다.

일단 항상 말하지만, 문제를 읽고 -> 대충 문제를 푸는 로직을 작성해보고 -> 시간복잡도 내에 해결이 가능한지 확인

이 순서대로 진행해봐야한다.
문제 1번으로 예시를 들어보자.

여기서 합승을 하는 조건때문에 플로이드 와샬 알고리즘을 써야한다고 바로알았는데 S에서 A까지 S에서 B까지 최소로 가는 알고리즘들은 많다. 다익스트라 플로이드 와샬 최소신장트리 등등등 많은데,

일단 합승을 하게 되면,

• S에서 출발하면 1까지 합승을 하고 헤어져서 1에서 6까지 1에서 2까지 갈지, * S에서 출발하여 5까지 합승을 하고 헤어져서 5에서 6까지, 5에서 2까지 갈지,
• S에서 출발하여 3까지 합승을 하고 헤어져서 3에서 2까지, 3에서 6까지 갈지

이 경우의 수를 모두 살펴봐서 최솟값을 살펴봐야한다는점이다.
즉 모든 노드에서 A와B의 위치까지 가는 최소값을 찾아야하므로 플로이드 와샬 알고리즘을 써야한다고 생각했다.

플로이드 와샬을 쓰는순간 일단 O(N^3)이니까 노드가 200개면 8000000번은 썻다.

그러면 일단 1억번 안쪽이니까 된다 생각하고 코드를 짯다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

long long graph[201][201];

int solution(int n, int S, int A, int B, vector<vector<int>> fares) {
    int answer = 0;
    
    for(int i=0;i<201;i++){
        for(int j=0;j<201;j++){
            if(i==j){graph[i][j]=0;}
            else{
            graph[i][j]=4*1e7;
            }
        }
    }

일단 그래프를 초기화하는데 4*1e7으로 초기화했다. 이것도 고민을 쫌 했는데 100,000이 최대 경로인데 만약에 200개를 다 돌고 다시 그 노드부터 A까지 가는 경우까지 계산하였다.

    for(int i=0;i<fares.size();i++){
        int a = fares[i][0];
        int b = fares[i][1];
        int cost = fares[i][2];
        graph[a][b]=cost;
        graph[b][a]=cost;
    }
    

해당 fares에 따라 초기화를 해주고,

  for(int k=1;k<=n;k++){
        for(int a=1;a<=n;a++){
            for(int b=1;b<=n;b++){
                graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b]);
            }
        }
    }

다익스트라를 적용시킨다음에,

   long long max = graph[S][A]+graph[S][B];
    
    for(int i=1;i<=n;i++){
        long long tmp = graph[S][i] + graph[i][A]+graph[i][B];
        if(tmp<max) max = tmp;
    }
    

일단 max값을 합승을 안하고 가는 조건으로 설정한후에 graph[s][i]는 i까지 합승을하고 그다음에 i부터 A와B로 따로가는 방식으로 요금을 계산하고 max와 비교를 해줬다.

정답코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

long long graph[201][201];

int solution(int n, int S, int A, int B, vector<vector<int>> fares) {
    int answer = 0;
    
    for(int i=0;i<201;i++){
        for(int j=0;j<201;j++){
            if(i==j){graph[i][j]=0;}
            else{
            graph[i][j]=4*1e7;
            }
        }
    }
    
    for(int i=0;i<fares.size();i++){
        int a = fares[i][0];
        int b = fares[i][1];
        int cost = fares[i][2];
        graph[a][b]=cost;
        graph[b][a]=cost;
    }
    
    for(int k=1;k<=n;k++){
        for(int a=1;a<=n;a++){
            for(int b=1;b<=n;b++){
                graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b]);
            }
        }
    }
    
    
    
    long long max = graph[S][A]+graph[S][B];
    
    for(int i=1;i<=n;i++){
        long long tmp = graph[S][i] + graph[i][A]+graph[i][B];
        if(tmp<max) max = tmp;
    }
    
    return max;
}