문제 링크

문제 간단 해석

다수의 출발점에서, 다수의 도착점으로 향하는 문제.
진행 도중 다른 출발점을 들리거나, 도착점을 지나쳐 더 진행할 수 없다.

풀이 코드

def solution(n, paths, gates, summits):
    field = {}
    
    for A, B, time in paths:
        for x, y in ((A, B), (B, A)):
            try:
                field[x].append((y, time))
            except:
                field[x] = [(y, time)]
    
    intensity = [10000001] * (n + 1)
    
    for gate in gates:
        intensity[gate] = 0
    
    check = set(summits)
    stack = gates
    
    while stack:
        target = set()
        
        while stack:
            now = stack.pop()

            for to, time in field[now]:
                max_time = max(intensity[now], time)

                if intensity[to] > max_time:
                    intensity[to] = max_time
                    
                    if to not in check:
                        target.add(to)

        stack = list(target)
        
    return min([[summit, intensity[summit]] for summit in summits], key=lambda x: (x[1], x[0]))
        

해석

출발점과 도착점이 여러 개라 처음 접했을 땐 조금 생소했고, 나눠서 출발시키는 방식을 구현했는데 역시나 시간초과로 이어졌다.
따라서 한꺼번에 출발시키는 방법을 도입했다.

지도 만들기

field = {}

for A, B, time in paths:
    for x, y in ((A, B), (B, A)):
        try:
            field[x].append((y, time))
        except:
            field[x] = [(y, time)]

방향성이 따로 없기 때문에, 양 쪽 모두 갈 수 있도록 길을 생성했다.
try, except를 활용해 defaultdict처럼 돌아갈 수 있게 했다.

최소거리 배열 만들기

intensity = [10000001] * (n + 1)

for gate in gates:
	intensity[gate] = 0

최소거리를 기록할 배열을 생성했다.
또한 시작점은 0으로 세팅하였다.

도착지점들과 시작지점 지정

check = set(summits)
stack = gates

도착점을 체크할 목적으로 set으로 변환시켰다.
또한 시작점에서 시작할 수 있도록 stack에 gates를 지정했다. 하나씩 빼면서 출발시킬 것이다.
어차피 list라 reference로 지정되어서 gates에서 빠질 텐데 왜 그렇게 했어요?
gates라는 이름을 while문에 쓰니 흐름이 좀 눈에 안들어와서 따로 이름을 stack으로 뒀다.

도착지점을 향해 전진

while stack:
    target = set()

    while stack:
        now = stack.pop()

        for to, time in field[now]:
            max_time = max(intensity[now], time)

            if intensity[to] > max_time:
                intensity[to] = max_time

                if to not in check:
                    target.add(to)

	stack = list(target)

return min([[summit, intensity[summit]] for summit in summits], key=lambda x: (x[1], x[0]))

stack에서 하나씩 빼며 해당 장소에서 갈 수 있는 곳을 탐색한다. (stack.pop() 대신 foreach로 했으면 가독성도 높고, 더 괜찮은 코드가 나왔을 것 같다.)
갈 수 있는 장소를 찾아 진행하되, 내가 들고 있는 값(휴식 없이 이동해야 하는 시간 중 가장 긴 시간)이 해당 장소에 기록된 시간보다 작을 때만 전진하기로 했다.
또한 해당 장소가 도착점이 아니라면 target에 넣어주기로 했다. set이기 때문에, 중복된 장소에 동시도착을 해도 최솟값을 든 채 한번만 진행하게끔 했다.

한 루프가 끝나면, 이번에 도착한 지점들에서 다시금 출발하게끔 했다.

더 이상 진행할 수 있는 길이 없다면, 모든 도착점 중 가장 intensity가 낮으며 index가 작은 값을 출력하게끔 했다.