신호등이 있는 그래프가 주어질 때 1부터 n으로 가는 경로 중에서 두번째로 짧은 경로를 구하는 문제.

Solution

일단 신호등이 change 마다 바뀌는데 다시 보면 시간이 change의 짝수 배이면 초록불, change의 홀수 배이면 빨간불이다.
이제 두번째로 짧은 경로를 구해야 하는데 마지막 도시에 두번째로 도착한 시간이 두번째로 짧은 경로가 된다. (가까운 순으로 방문하게 되므로)
다익스트라로 구현했고 visitcnt를 통해 총 몇번 방문했는지 체크한다. 두번째로 짧은 경로이므로 모든 도시는 최대 2번까지 방문할 수 있다. (그 이상은 경로가 길어지므로 고려할 필요가 없음)

처음에는 두번 방문까지 된다고 짰지만 구현이 꽤 까다로움. 에디토리얼 보고 클리어.

Source Code

from sortedcontainers import SortedList

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        pq = [(0, 1)]
        graph = defaultdict(list)
        visitcnt = defaultdict(int)
        distance = [[float('inf')] * 2 for _ in range(n + 1)]
        distance[1][0] = 0

        # time의 짝수 배수와 홀수 배수 사이면 바로 출발
        # 홀수 배수와 짝수 배수 사이면 짝수 배수까지 대기
        def caltime(dist):
            if (dist // change) % 2 == 0:
                return dist
            return (dist // change) * change + change

        for e in edges:
            graph[e[0]].append(e[1])
            graph[e[1]].append(e[0])

        while len(pq) > 0:
            current = heapq.heappop(pq)
            [d, c] = current
            
            visitcnt[c] += 1
            if visitcnt[c] >= 2 and c == n:
                return d
            
            for next in graph[c]:
                if visitcnt[next] >= 2:
                    continue
                
                cal = caltime(d) + time
                if distance[next][0] > cal:
                    distance[next][1] = distance[next][0]
                    distance[next][0] = cal
                    heapq.heappush(pq, (cal, next))
                elif distance[next][1] > cal and distance[next][0] < cal:
                    distance[next][1] = cal
                    heapq.heappush(pq, (cal, next))
                

        return 0

2045. Second Minimum Time to Reach Destination

Problem link

Problem Summary

Solution

Source Code