Minimum Fuel Cost to Report to the Capital

매개변수로 양방향 그래프의 간선을 나타내는 roads 벡터와 차량의 좌석 수 seats를 받는다.

인덱스를 기준으로 도시 노드들이 존재하고 0번 노드는 수도이다.

차량은 한 도시에서 근접한 도시로 이동할 때 기름을 1씩 소모하며,

모든 도시에서 한명씩 수도까지 차량을 타고 이동할 때 최소 기름 비용을 구하는 문제이다.

이 때 도시에 차량이 두 대 이상 모였을 때 남는 좌석이 있다면 동승하게 된다.

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        
        int length = roads.size() + 1;
        vector<vector<int>> graph(length);

        for (auto& road : roads)
        {
            graph[road[0]].push_back(road[1]);
            graph[road[1]].push_back(road[0]);
        }

        long long result{0};
        if (graph.empty())
        {
            return result;
        }

        vector<bool> visited(length);
        visited[0] = true;

        SearchDFS(0, 0, graph, visited, seats, result);

        return result;
    }
private:
    long long SearchDFS(int index, int distance, vector<vector<int>>& graph, vector<bool>& visited, int& maxSeats, long long& result)
    {
        long long persons{1};
        int length = graph[index].size();
        for (int i = 0; i < length; ++i)
        {
            if (visited[graph[index][i]])
            {
                continue;
            }

            visited[graph[index][i]] = true;

            persons += SearchDFS(graph[index][i], distance + 1, graph, visited, maxSeats, result);
        }

        auto division = std::lldiv(persons, maxSeats);
        long long cars = division.quot;
        long long leftPersons = division.rem;

        if (leftPersons)
        {
            ++cars;
        }

        if (index != 0)
        {
            result += cars;
        }

        return persons;
    }
};