[LeetCode] 3243. Shortest Distance After Road Addition Queries I

https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i/description/

leetcode - Shortest Distance After Road Addition Queries I

문제 유형: 최단 경로, 그래프, 다익스트라, 다이나믹 프로그래밍

문제 난이도: Medium

 

문제

You are given an integer n and a 2D integer array queries.

There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1.

queries[i] = [ui, vi] represents the addition of a new unidirectional road from city ui to city vi. After each query, you need to find the length of the shortest path from city 0 to city n - 1.

Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.

 

정수 n과 2D정수배열 queries가 주어집니다.

도시가 0에서 N-1까지 있습니다. i번째 도시에서 i+1도시까지 무방향 길이 있습니다.

queries[i] = [u, v]의 꼴로 있고, u에서 v로 가는 길을 추가합니다.

쿼리 이후에, 당신은 0에서 n-1까지 가는 가장 짧은 길이를 구해야 합니다.

answer배열에 각 쿼리 이후의 최단거리를 담아서 반환하시오.

 

풀이

단순히 bfs를 이용하면 된다.

매번 쿼리에 있는 간선을 그래프에 추가해서, 0에서 n-1까지의 bfs를 한다.

조심할 점은, visited를 안쓰면 TLE에 걸리므로, visited로 이미 간 도시에 대해서는 재방문 하지 않도록 하자.

 

또는, dp + dfs를 이용한 방법도 있다.

https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i/solutions/6087071/video-beats-100/

의 1번 풀이를 참고하면 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int bfs(vector<vector<int>>& graph, int n) {
        queue<pair<int, int>> q;
        q.push({0, 0});
        vector<bool>visited(n);
        visited[0] = true;
        while(!q.empty()) {
            auto [curr, dist] = q.front();
            q.pop();
            if(curr == n-1) return dist;

            for(const auto &next : graph[curr]) {
                if(!visited[next]) {
                    q.push({next, dist+1});
                    visited[next] = true;
                }
            }
        }
        return -1;
    }
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> graph(n);
        for(int i = 0; i < n-1; ++i) {
            graph[i].push_back(i+1);
        }

        vector<int> ans;
        for(const auto &query : queries) {
            graph[query[0]].push_back(query[1]);
            ans.push_back(bfs(graph, n));
        }
        return ans;
    }
};