문제 링크

내 코드

매 번 재계산해도 가능할 것이라 생각했음.

• 88ms, 137.06MB

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        // 매 번 BFS로 재계산?
        // 500 * 500 * 500
        vector<vector<int>> edge(n);
        // default
        for(int i{};i<n - 1;++i) {
            edge[i].push_back(i + 1);
        }
        vector<int> answer;
        for(auto& query : queries) {
            int u = query[0], v = query[1];
            // There are no repeated roads among the queries.
            edge[u].push_back(v);

            vector<int> dist(n, 0);
            dist[0] = 1;
            queue<int> q; q.push(0);
            while(!q.empty()) {
                for(int s{}, e = static_cast<int>(q.size()); s < e; ++s) {
                    int now = q.front(); q.pop();

                    for(int next : edge[now]) {
                        if(dist[next]) continue;
                        dist[next] = dist[now] + 1;
                        q.push(next);
                    }

                    if(dist[n - 1]) break;
                }
                if(dist[n - 1]) break;
            }
            answer.push_back(dist[n - 1] - 1);
        }
        return answer;
    }
};

Solution

Approach 1: Breadth First Search (BFS)

• 123ms, 114.15MB
• Complexity
  • Let n be the number of cities and q the number of queries.
  • Time Complexity: $O(q \times (n + q))$
  • Space Complexity: $O(n + q)$

class Solution {
public:
    // Helper function to perform BFS and find the number of edges in the
    // shortest path from node 0 to node n-1
    int bfs(int n, vector<vector<int>>& adjList) {
        vector<bool> visited(n, false);
        queue<int> nodeQueue;
        // Start BFS from node 0
        nodeQueue.push(0);
        visited[0] = true;

        // Track the number of nodes in the current layer and the next layer
        int currentLayerNodeCount = 1;
        int nextLayerNodeCount = 0;
        // Initialize layers explored count
        int layersExplored = 0;

        // Perform BFS until the queue is empty
        while (!nodeQueue.empty()) {
            // Process nodes in the current layer
            for (int i = 0; i < currentLayerNodeCount; ++i) {
                int currentNode = nodeQueue.front();
                nodeQueue.pop();

                // Check if we reached the destination node
                if (currentNode == n - 1) {
                    return layersExplored;  // Return the number of edges in the
                                            // shortest path
                }

                // Explore all adjacent nodes
                for (auto neighbor : adjList[currentNode]) {
                    if (visited[neighbor]) continue;
                    nodeQueue.push(
                        neighbor);  // Add neighbor to the queue for exploration
                    nextLayerNodeCount++;  // Increment the count of nodes in
                                           // the next layer
                    visited[neighbor] = true;
                }
            }

            // Move to the next layer
            currentLayerNodeCount = nextLayerNodeCount;
            nextLayerNodeCount = 0;  // Reset next layer count
            layersExplored++;  // Increment the layer count after processing the
                               // current layer
        }

        return -1;  // Algorithm will never this point
    }

    vector<int> shortestDistanceAfterQueries(int n,
                                             vector<vector<int>>& queries) {
        vector<int> answer;
        vector<vector<int>> adjList(n, vector<int>(0));

        // Initialize the graph with edges between consecutive nodes
        for (int i = 0; i < n - 1; i++) {
            adjList[i].push_back(i + 1);
        }

        // Process each query to add new roads
        for (auto& road : queries) {
            int u = road[0];
            int v = road[1];
            adjList[u].push_back(v);  // Add road from u to v
            // Perform BFS to find the shortest path after adding the new road
            answer.push_back(bfs(n, adjList));
        }

        return answer;
    }
};

Approach 2: Recursive Dynamic Programming (Top-Down)

• 96ms, 52.64MB
• Complexity
  • Let n be the number of cities and q the number of queries.
  • Time Complexity: $O(q \times (n + q))$
  • Space Complexity: $O(q \times (n + q))$

class Solution {
public:
    // Recursive function to find the minimum distance from the current node to
    // the destination node (n-1)
    int findMinDistance(vector<vector<int>> &adjList, int n, int currentNode,
                        vector<int> &dp) {
        // We've reached the destination node
        if (currentNode == n - 1) return 0;

        // If this node has already been computed, return the stored value
        if (dp[currentNode] != -1) return dp[currentNode];

        int minDistance = n;

        for (int neighbor : adjList[currentNode]) {
            // Recursively find the minimum distance from the neighbor to the
            // destination
            minDistance =
                min(minDistance, findMinDistance(adjList, n, neighbor, dp) + 1);
        }

        // Store the computed minimum distance in the dp array and return it
        return dp[currentNode] = minDistance;
    }

    vector<int> shortestDistanceAfterQueries(int n,
                                             vector<vector<int>> &queries) {
        vector<int> dp(
            n, -1);  // DP array to store minimum distances from each node
        vector<vector<int>> adjList(n, vector<int>(0));

        // Initialize the graph with edges between consecutive nodes
        for (int i = 0; i < n - 1; i++) {
            adjList[i].push_back(i + 1);
        }

        vector<int> answer;

        // Process each query to add new edges
        for (auto &road : queries) {
            int u = road[0];
            int v = road[1];

            // Add the directed edge from u to v
            adjList[u].push_back(v);

            // Find the minimum distance from the starting node (0) to the
            // destination (n-1)
            answer.push_back(findMinDistance(adjList, n, 0, dp));

            // Clear and resize the dp array
            dp.clear();
            dp.resize(n, -1);
        }

        return answer;  // Return the results for each query
    }
};

Approach 3: Iterative Dynamic Programming (Bottom-Up)

• 72ms, 79.24MB
• Complexity
  • Let n be the number of cities and q the number of queries.
  • Time Complexity: $O(q \times (n + q))$
  • Space Complexity: $O(n + q)$

class Solution {
public:
    // Function to find the minimum distance from node 0 to node n-1
    int findMinDistance(vector<vector<int>> &adjList, int n) {
        vector<int> dp(n);
        dp[n - 1] = 0;  // Base case: distance to destination (n-1) is 0

        // Iterate from the second last node down to the first node
        for (int currentNode = n - 2; currentNode >= 0; currentNode--) {
            int minDistance = n;
            // Explore neighbors to find the minimum distance
            for (auto neighbor : adjList[currentNode]) {
                minDistance = min(minDistance, dp[neighbor] + 1);
            }
            dp[currentNode] = minDistance;  // Store the calculated distance for
                                            // the current node
        }
        return dp[0];
    }

    vector<int> shortestDistanceAfterQueries(int n,
                                             vector<vector<int>> &queries) {
        vector<int> answer;
        vector<vector<int>> adjList(n, vector<int>(0));

        // Initialize edges between consecutive nodes
        for (int i = 0; i < n - 1; i++) {
            adjList[i].push_back(i + 1);
        }

        // Process each query to add new edges
        for (auto &road : queries) {
            int u = road[0];
            int v = road[1];
            adjList[u].push_back(v);  // Add the directed edge from u to v

            // Calculate the minimum distance after adding the new edge
            answer.push_back(findMinDistance(adjList, n));
        }
        return answer;
    }
};