[LeetCode] 2045. Second Minimum Time to Reach Destination

https://leetcode.com/problems/second-minimum-time-to-reach-destination/description/?envType=daily-question&envId=2024-07-28

leetcode - Second Minimum Time to Reach Destination

문제 유형 : BFS, 최단서리, 큐

문제 난이도 : Hard

 

문제

A city is represented as a bi-directional connected graph with n vertices where each vertex is labeled from 1 to n (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. The time taken to traverse any edge is time minutes.

Each vertex has a traffic signal which changes its color from green to red and vice versa every change minutes. All signals change at the same time. You can enter a vertex at any time, but can leave a vertex only when the signal is green. You cannot wait at a vertex if the signal is green.

The second minimum value is defined as the smallest value strictly larger than the minimum value.

• For example the second minimum value of [2, 3, 4] is 3, and the second minimum value of [2, 2, 4] is 4.

Given n, edges, time, and change, return the second minimum time it will take to go from vertex 1 to vertex n.

 

n개의 도시들이 1 ~ n의 번호가 매겨진 채로 있다.

간선 배열 edges에는 edges[i] = [u_i, v_i]가 있고, u_i와 v_i가 양방향 연결이 되어있다는 의미로 담겨 있는 2D 배열이다.

각각의 간선을 지나는 데에는 time만큼 걸린다.

 

길을 건너는 데는 신호의 영향을 받는다. 도시에 도착하는데 따로 제한은 없지만, 출발하는데에는 빨간불에 출발하지 못하는 제한이 있다.

처음에는 초록불로 시작하고, 초록불에는 기다릴 수 없이 바로 출발해야 한다. 매 change초마다 바뀐다.

1에서 시작해서 n까지 도착하는 데 걸리는 두 번째로 빠른 시간을 구하시오.

 

풀이

우선, edges를 이용해서 인접 리스트를 만든다.

1에서 출발해서 각 노드까지 도착하는 데 걸리는 시간을 담는 배열 firstDist, secondDist를 만든다.

{도시번호, 걸린시간}을 저장하는 큐 q를 만든다.

처음에 q에 {1, 0}을 넣고, firstDist[1] = 0으로 시작한다.

 

큐를 통해서 bfs순회를 하는데, 다음 노드에 도착할 때의 시간을 고려하려면 신호를 고려해야 한다.

만약 ((현재 시간) / (change) % 2)가 1이면, 현재 빨간불이란 뜻으로, 추가로 change - (현재시간 % change)만큼 기다려야 한다.

(왜 이런 수식이 나오는지는 생각해보면 알것이다.)

간선을 지나는데에는 time이 걸린다.

즉, 다음 노드로 가는 데 걸리는 시간은 (현재 노드까지 오는데 걸리는 시간) + (현재시간) / (change) % 2 == 1 ? change - (현재시간 % change) : 0 + time이다.

 

다음 노드로 가는 데 걸리는 시간을 nextTime, 다음 노드를 nextNode라 했을 때,

1. nextTime < firstTime[nextNode]인 경우, secondTime[nextNode]에 firstTime[nextNode]를 저장하고, firstTime에 nextTIme을 저장한다.
   그리고, 큐에 {nextNode, nextTime}을 넣는다.
2. nextTime > firstTime[nextNode] && secondTime[nextNode] > nextTime인 경우, secondTime[nextNode] 에 nextTime을 저장한다. 
   그리고, 큐에 {nextNode, nextTime}을 넣는다.

큐가 비고 나면, firstTime과 secondTime에는 각각 가장 빠른 시간과 두 번째로 빠른 시간이 저장되어 있는데, secondTime[n]을 반환하면 된다.

 

코드

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 secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        vector<vector<int>> graph(n + 1);
        vector<int> firstDist(n+1, INT_MAX-1);
        vector<int> secondDist(n+1, INT_MAX);
        
        for (const auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        queue<pair<int, int>> q;
        q.push({1, 0});
        firstDist[1] = 0;
        secondDist[1] = INT_MAX-1;

        while(!q.empty()) {
            int currNode = q.front().first;
            int currTime = q.front().second;
            q.pop();

            for(const auto &nextNode : graph[currNode]) {
                int waitTime = (currTime / change) % 2 == 1? change - (currTime % change) : 0;
                int nextTime = currTime + waitTime + time;
                if(firstDist[nextNode] > nextTime) {
                    q.push({nextNode, nextTime});
                    secondDist[nextNode] = firstDist[nextNode];
                    firstDist[nextNode] = nextTime;
                } else if(nextTime > firstDist[nextNode] && secondDist[nextNode] > nextTime) {
                    q.push({nextNode, nextTime});
                    secondDist[nextNode] = nextTime;
                }
            }
        }

        return secondDist[n];
    }
};