[2021 카카오 블라인드 코딩테스트] 택시 합승 (c++)

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

프로그래머스

위의 문제에 대한 풀이입니다.

 

이번엔 오답+ 정답 코드를 포스팅하는데, 우선 정답 먼저 보겠습니다.

택시합승이란 문제는 결국 어느지점까지 합승할지? 를 해결하면 풀 수 있습니다.

따라서 플로이드 와샬 알고리즘을 통하여 모든 노드들 간의 최단거리를 찾고, 어떤 합승지점에서 최소 값이 나오는지 linear 탐색을 통해 찾으면 해결됩니다. 

아래는 해결 코드입니다.

#include <string>
#include <vector>
#include<queue>
#include<queue>
#include<memory.h>
#include<iostream>
using namespace std;
#define inf 987654321
int dist[300][300];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = inf;
        }
    }
    for (auto it : fares) {
        int p1 = it[0], p2 = it[1], cost = it[2];
        dist[p1][p2] = cost;
        dist[p2][p1] = cost;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] == inf || dist[k][j] == inf) continue;
                if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    int min = dist[s][s] + dist[s][a] + dist[s][b];

    for (int i = 1; i <= n; i++) {
        if (dist[s][i] == inf || dist[i][a] == inf || dist[i][b] == inf)continue;

        if (min > dist[s][i] + dist[i][a] + dist[i][b])
            min = dist[s][i] + dist[i][a] + dist[i][b];
    }
    answer = min;
    return answer;
}

여기서 조금더 시간복잡도를 줄이고 싶다면, 다익스트라를 사용해도 괜찮은데,결국 매커니즘은 유사합니다.

 

1 )출발점 -> 합승 종료지점    

2) 합승 종료지점 -> a의 집 

3)  합승 종료지점 -> b의집       

 

주어진 n개의 위치를 모두 합승 종료지점으로 두고 1,2,3 번 케이스를 각각 다익스트라를 통하여 구한 뒤, 합치고, 이값이

최소가되는 합승종료지점이 최소 비용을 만들어내는 합승종료지점이 되므로 출력하면 됩니다.

 

 

<Extra>

이번에는 번외로 제가 했던 풀이에 해 설명하겠습니다.

제가 실수한 부분은 두 사람이 꼭 1개의 택시만 사용할거라고 착각한 부분입니다.

둘이 서로 다른 택시를 탑승할 수 있다는 것으로 생각하고 제가 구한 풀이는 단순히

 

1) 출발점 -> A의 집    or  출발점-> B의 집     중 더 가까운 집의 최단거리

2) A와 B의 집 사이의 최단거리

 

위 2가지를 구해 더한 것입니다. 

이렇게되면 제가 구한 값은 "택시 1대" 를 통해 시작지점에서 A와 B의 집 둘 모두 도착할 수 있는 최단거리입니다.

본 문제에 대해서는 틀린 풀이 이지만, 응용될만한 여지가 있을 것 같아 추가로 올려봅니다!

코드는 아래와 같습니다.

#include <string>
#include <vector>
#include<queue>
#include<queue>
#include<memory.h>
#include<iostream>
using namespace std;
#define inf 100001
typedef struct {
    int from, to, cost;

}edge;
int dist[200][200];
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    for (int i = 0; i < 200; i++) {
        for (int j = 0; j < 200; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = inf;
        }
    }


    //S>A, S>B
    priority_queue < pair<int, pair<int, int>> >pq;
    for (auto it : fares) {
        if (it[0] == s)
            pq.push({ -it[2],{it[0],it[1]} });

        if (it[1] == s)
            pq.push({ -it[2],{it[1],it[0]} });

    }
    
    while (!pq.empty()) {
        int from = pq.top().second.first, to = pq.top().second.second, cost = -pq.top().first;
        pq.pop();
        //cout<<from<<" "<<to<<" "<<cost<<endl;
        //cout<<dist[s][to]<<" "<<dist[s][from]<<endl;
        if (dist[s][to] > dist[s][from] + cost && dist[s][from] != inf) {

            dist[s][to] = dist[s][from] + cost;

            for (auto it : fares) {
                if (it[0] == to)
                    pq.push({ -it[2],{it[0],it[1]} });

                if (it[1] == to)
                    pq.push({ -it[2],{it[1],it[0]} });
            }
        }
    }
    int StoA = dist[s][a];
    int StoB = dist[s][b];






    //A>B
    pq = priority_queue < pair<int, pair<int, int> > >();
    for (int i = 0; i < 200; i++) {
        for (int j = 0; j < 200; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = inf;
        }
    }

    for (auto it : fares) {
        if (it[0] == a)
            pq.push({ -it[2],{it[0],it[1]} });

        if (it[1] == a)
            pq.push({ -it[2],{it[1],it[0]} });
    }
  
    while (!pq.empty()) {
        int from = pq.top().second.first, to = pq.top().second.second, cost = -pq.top().first;
        pq.pop();

        //cout<<dist[a][to]<<" "<<dist[a][from]<<endl;
        if (dist[a][to] > dist[a][from] + cost && dist[a][from] != inf) {

            dist[a][to] = dist[a][from] + cost;

            for (auto it : fares) {
                if (it[0] == to)
                    pq.push({ -it[2],{it[0],it[1]} });

                if (it[1] == to)
                    pq.push({ -it[2],{it[1],it[0]} });
            }
        }
    }

    int AtoB = dist[a][b];

    int low;
    if (StoA > StoB) low = StoB;
    else low = StoA;
    int together = low + AtoB, isorate = StoA + StoB;
    if (together < isorate) answer = together;
    else answer = isorate;


    return answer;
}