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

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

• 재풀이

// https://school.programmers.co.kr/learn/courses/30/lessons/72413
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

map<int, set<int>> ft_process_link(int n, vector<vector<int>> fares) {
    map<int, set<int>> link_data;

    for (int i = 1; i <= n; i++) {
        set<int> temp;
        for (int j = 0; j <= fares.size(); j++) {
            if (fares[j][0] == i) {
                temp.insert(fares[j][1]);
            }
            if (fares[j][1] == i) {
                temp.insert(fares[j][0]);
            }
        }
        link_data.insert(make_pair(i, temp));
    }
}

map<set<int>, int> ft_process_price(vector<vector<int>> fares) {
    map<set<int>, int> price_data;

    for (int i = 0; i < fares.size(); i++) {
        set<int> temp;
        temp.insert(fares[i][0]);
        temp.insert(fares[i][1]);
        price_data.insert(make_pair(temp, fares[i][2]));
    }
    return price_data;
}

void ft_bfs() {
    // 처음부터 합승, 비합승 모두 탐색

    ft_candidate_duo();
    ft_candidate_solo();
    // 갔던 지점은 다시 돌아가지 않음(이중과금 발생)
    // 갈 수 있는 루트가 존재하지 않는경우(막다른 경우) 후보에서 제외

    // map을 써야겠지? 왜냐면 택시비를 저장은 해야할테니깐
    // 도착과 출발을 검색하는 함수도 만들어야함.

    // fare 자료를 벡터벡터 보다는 순서없는 자료구조에 담는게 더 낫지않을까?
    // map<set<int>, int> 이런식으로... 그럼 set을 어떻게 찾지?
    // 아니면 간선과의 관계만 바로바로 리턴해줄수 있는 자료구조가 있을까? -> map<set<int>>

}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    map<int, set<int>> link_data = ft_process_link(n, fares);
    map<set<int>, int> price_data = ft_process_price(fares);

    ft_bfs(link_data, price_data, );

    return answer;
}

int main() {
    vector<vector<int>> fares1 = {
        {4, 1, 10},
        {3, 5, 24},
        {5, 6, 2},
        {3, 1, 41},
        {5, 1, 24},
        {4, 6, 50},
        {2, 4, 66},
        {2, 3, 22},
        {1, 6, 25}
    };
    cout << "ex01: " << solution(6, 4, 6, 2, fares1) << endl;

    vector<vector<int>> fares2 = {
        {5, 7, 9},
        {4, 6, 4},
        {3, 6, 1},
        {3, 2, 3},
        {2, 1, 6}
    };
    cout << "ex02: " << solution(7, 3, 4, 1, fares1) << endl;

    vector<vector<int>> fares3 = {
        {2, 6, 6},
        {6, 3, 7},
        {4, 6, 7},
        {6, 5, 11},
        {2, 5, 12},
        {5, 3, 20},
        {2, 4, 8},
        {4, 3, 9}
    };
    cout << "ex03: " << solution(6, 4, 5, 6, fares1) << endl;
}```