[Programmers] 2021 kakao blind - 합승 택시 요금

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

코딩테스트 연습 - 합승 택시 요금

풀이 방법 : 플로이드, 다익스트라

​

나의 사고 과정

1. undirected, s에서 a,b를 지나는 짧은거리의 합

-> 다익스트라 생각을 함.

-> 근데 dest가 1개가 아니고 2개다. 예시를 보니 어떤 다른 점에서도 a,b로 갈 수 있다.

모든 최단거리들을 구해놓고 더하면 되겠다

-> Floyd로 하면 되겠다고 생각함. but 아직 개념만 알고 구현을 눈감고 할 수 있는 상태가 아님. 그래서 이 방법을 PASS함.

​

2. 그러면 floyd를 할줄 모르니까 다익스트라를 모든 점에 대해서 돌리면 되는게 아닌가? 생각함.

v = 200, E = 2만개정도..

이러면 O(V * ElogE) 수준이라서, E가 2만개일경우 30만정도..

즉 200 * 30만 = 6천만정도.. 그래서 될 것 같았다. ? 가 아니고

​

처음에 뇌가 어디 구멍이 났는지 O(ElogE)^V 로 생각했다. ElogE를 왜 곱을 했는지 모르겠는데, for문에 모든 정점 넣고 돌리는거라 그냥 V번만큼 반복인데, 그래서 저 방법을 하면 시간이 초과날줄 알고 안했다. 정신이 나간놈이었다.

​

그래서 다르게 생각을 했다.

s,a,b에 대해서 다익스트라를 돌리고

s->a->b, a->s->b, b->a->s 케이스를 구해서 최솟값을 찾기로 했다.

​

다익스트라를 구현하는데 20분인가 걸렸다.

어디서 문제가 생겼는가?

if( dist[next_vertex] > cur_weight + dist[prev_vertex])

요걸 i.second, i.first, v 이런식으로 둬서 헷갈려서 헤맸다. 다음번엔 주의해야겠다. (이제 10분 안에 컷 낼 수 있을거다)

​

아무튼 어찌저찌 구현에 성공하고,

min( dist[s][a] + dist[s][b], dist[a][b] + dist[a][s], dist[b][a] + dist[b][s])를 해보니까

테케가 2개가 맞았다. 근데 1번이 틀렸다. 알고보니까 1번은 다른 지점에서 만나서 가는경우이다. 그래서 이걸 어떻게 하지 했다.

​

아무리 생각해도 다 구해봐야 하는거 아닌가? 생각했다.

​

3. 결론

O(V*ElogE)로 먼저 풀이에 성공을 했다.

모든 경로를 다 구한다음에

for(int i = 1; i <= n; i++)

min( arr[i][a] + arr[i][s] + arr[i][b]);

이렇게 하면 모든 점에서 다 가보는게 되니까..

​

무방향이므로, 저렇게 양방향으로 값을 받아야한다.

이번에 Prim으로 연습문제 풀어보면서 저걸로 한번 틀려서 이제 기억에 남는다.

 

#include<bits/stdc++.h>

using namespace std;
int INF = 2e+9;
int dist[205][205];
vector<pair<int,int>> vertex[205];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    int w,v;
    int sz = fares.size();
    for(int i = 0; i < sz; i++)
    {
        vertex[fares[i][0]].push_back({fares[i][1],fares[i][2]});
        vertex[fares[i][1]].push_back({fares[i][0],fares[i][2]});
    }
    for(int i = 1; i <= n; i++)
        fill(dist[i]+1,dist[i]+n+1,INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    int temp;
    for(int i = 1; i <= n; i++)
    {
        pq.push({0,i});
        dist[i][i] = 0;
        while(!pq.empty())
        {
            tie(w,v) = pq.top(); pq.pop();

            if(w != dist[i][v]) continue;
            for(auto x : vertex[v]){
                // i.first = v, i.second = w
                if(dist[i][x.first] > x.second + dist[i][v] ){ // 시작점 + weight 
                    dist[i][x.first] = x.second + dist[i][v];
                    pq.push({dist[i][x.first], x.first});
                }
            }
        }
    }
    int min_num = INF;
    for(int i = 1; i <= n; i++)
    {
        temp = dist[i][s] + dist[i][a] + dist[i][b];
        if(temp < min_num) min_num = temp;
    }
    return min_num;
}

약 90분이 소모가 됐다.

이제 잘못된걸 풀어보기로 했다.

​

저 풀이가 맛탱이가 간건 맞다. V가 작아서 운이 좋게 된거지..

​

내 풀이는

X가 모든 V일때

min(dist(S,X) + dist(X,A) + dist(X,B))

-> S에서 X로 가고, X에서 A로 가고, X에서 B로 갈 수 있으면 된다.

이걸 다 돌려본거다.

​

근데 이건 undirected 이다.

즉 A->B, B->A가 똑같다. 갑자기 이걸 보니까

dist(S,X) + dist(A,X) + dist(B,X)로 봐도 되겠다는 생각이 들었다.

​

따라서 처음에 내가 구했던 S,A,B에 대한 다익스트라에서

for(int i = 1; i <= n; i++)

{

min( ret , dist[s][i] + dist[a][i] + dist[b][i]);

}

를 하면 똑같은 결과를 얻을 수 있다고 생각했다.

​

이렇게 하면 O(3 * ElogE)에 해결이 가능했다.

실제로 돌려보니 시간차이가 굉~~장히 많이 났다.

#include<bits/stdc++.h>

using namespace std;
int INF = 2e+9;
int dist[3][205];
int pre[205];
vector<pair<int,int>> vertex[205];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
	int w,v;
	int sz = fares.size();
	for(int i = 0; i < sz; i++)
	{
		vertex[fares[i][0]].push_back({fares[i][1],fares[i][2]});
		vertex[fares[i][1]].push_back({fares[i][0],fares[i][2]});
	}
	for(int i = 0; i < 3; i++)
		fill(dist[i]+1,dist[i]+n+1,INF);
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	int temp;
	
	for(int i = 0; i < 3; i++)
	{
		if( i == 0){
			temp = s;
		}else if( i == 1){
			temp = a;
		}else{
			temp = b;
		}

		pq.push({0,temp});
		dist[i][temp] = 0;
		while(!pq.empty())
		{
			tie(w,v) = pq.top(); pq.pop();

			if(w != dist[i][v]) continue;
			for(auto x : vertex[v]){
				// i.first = v, i.second = w
				if(dist[i][x.first] > x.second + dist[i][v] ){ // 시작점 + weight 
					dist[i][x.first] = x.second + dist[i][v];
					pq.push({dist[i][x.first], x.first});
				}
			}
		}
	}
	// dist[0] -> s dist[1] -> a  dist[2] -> b;
	int min_num = INF;
	for(int i = 1; i <= n; i++)
	{
		min_num = min(min_num, dist[0][i] + dist[1][i] + dist[2][i]);
	}
    return min_num;
}

자료구조의 개념을 정확하게 생각하고 약간만 멈춰서 생각해보면 좀 더 좋은 아이디어가 있는것 같다.

모르면 일단 무식한풀이로..

​

플로이드 알고리즘도 스스로 짜봐야겠다.