최첨단 드론 배송 시스템은 n개의 물류 허브와, 각 허브를 잇는 양방향 항로 routes 정보로 구성됩니다. 각 항로는 [허브1, 허브2, 비행 거리]를 담고 있습니다.
하나의 타겟 허브 t가 고정된 상태에서, 드론이 따라야 할 비행 로그(logs)가 주어집니다. 이 logs는 드론이 이동할 항로의 비행 거리를 순서대로 담고 있는 절대적인 비행 계획입니다.
주어진 logs를 만족하는 모든 출발점을 찾아, 각 출발점에서 시작된 전체 배송 경로를 배열 형태로 반환하는 solution 함수를 완성하세요. 이때 타겟 t는 경로 규칙을 판단하기 위한 기준점으로만 사용되며, 실제 경로가 t를 방문하지 않아도 무방합니다. 각 경로는 거쳐간 허브 번호의 순서로 된 배열([출발 허브, ...])이어야 하며, 최종 결과는 출발 허브 번호를 기준으로 오름차순 정렬해야 합니다.
드론이 허브 a에서 b로, 비행 거리 w인 항로를 통과할 때 기록은 다음과 같이 남습니다.
w (양수)로 기록된 경우: 현재 비행한 항로(a, b)가, 현재 위치 a에서 최종 목적지 t까지 가는 최단 배송 경로 상에 포함될 때
-w (음수)로 기록된 경우: 현재 비행한 항로(a, b)가, 현재 위치 a에서 최종 목적지 t까지 가는 최단 배송 경로 상에 포함되지 않을 때
물류 허브의 수 n: 2 이상 500 이하
항로 정보 routes: [허브1, 허브2, 비행 거리] 형식의 2차원 배열
비행 거리: 1 이상의 정수
하나의 허브에 연결된 모든 항로의 비행 거리는 서로 다릅니다.
로그 logs: 길이가 1 이상 500 이하인, 0이 아닌 정수 배열
주어진 입력에 대해 유효한 경로는 반드시 하나 이상 존재합니다.
예시 1:
입력:
n = 6
routes = [[1,2,4], [1,3,1], [1,5,2], [1,6,3], [2,3,2], [2,5,1], [4,5,3], [4,6,1], [5,6,4]]
target = 1
logs = [1, -4, 2]
출력: [[3,1,2,3], [4,6,5,1]]
설명:
출발점: 3 (경로 3→1→2→3)
+1: 허브 3에서 w가 1인 항로는 3→1 입니다. dist(3,1) == 1 + dist(1,1) 이므로 최단경로가 맞습니다.
-4: 허브 1에서 w가 4인 항로는 1→2 입니다. dist(1,1) < 4 + dist(2,1) 이므로 최단경로 아닙니다.
+2: 허브 2에서 w가 2인 항로는 2→3 입니다. dist(2,1) == 2 + dist(3,1) 이므로 최단경로가 맞습니다.
출발점:4 (경로 4→6→5→1)
+1: 허브 4에서 w가 1인 항로는 4→6 입니다. dist(4,1) == 1 + dist(6,1) 이므로 최단경로가 맞습니다.
4: 허브 6에서 w가 4인 항로는 6→5 입니다. dist(6,1) < 4 + dist(5,1) 이므로 최단경로가 아닙니다.
+2: 허브 5에서 w가 2인 항로는 5→1 입니다. dist(5,1) == 2 + dist(1,1) 이므로 최단경로가 맞습니다.
예시 2:
입력:
n = 4
routes = [[1,2,10], [2,3,20], [3,4,30]]
target = 4
logs = [10, 20, 30]
출력: [[1, 2, 3, 4]]
설명:
로그가 [10, 20, 30]으로 모두 양수입니다. 이는 모든 이동이 현재 위치에서 타겟(4)까지 가는 최단 경로임을 의미합니다.
1번 허브에서 출발: 1 -> 2 (비행 거리 10)는 1에서 4로 가는 최단 경로의 일부입니다.
2번 허브에서: 2 -> 3 (비행 거리 20)는 2에서 4로 가는 최단 경로의 일부입니다.
3번 허브에서: 3 -> 4 (비행 거리 30)는 3에서 4로 가는 최단 경로의 일부입니다.
따라서 [1, 2, 3, 4] 경로가 조건을 만족합니다.
예시 3:
입력:
n = 4
routes = [[1,2,1], [1,3,10], [2,4,100], [3,4,1]]
target = 4
logs = [-1, -100]
출력: [[1, 2, 4]]
설명:
로그가 [-1, -100]으로 모두 음수입니다. 이는 모든 이동이 현재 위치에서 타겟(4)까지 가는 최단 경로가 아닌, 우회 경로임을 의미합니다.
1번 허브에서 출발: 비행 거리가 1인 1 -> 2 경로로 이동합니다. 1에서 4로 가는 최단 경로는 1 -> 3 -> 4 (총 11)이므로, 1 -> 2는 최단 경로가 아닙니다. (로그 -1 만족)
2번 허브에서: 비행 거리가 100인 2 -> 4 경로로 이동합니다. 2에서 4로 가는 최단 경로는 2 -> 1 -> 3 -> 4 (총 12)이므로, 2 -> 4는 최단 경로가 아닙니다. (로그 -100 만족)
따라서 [1, 2, 4] 경로가 조건을 만족합니다.
4
[[1,2,10],[2,3,20],[3,4,30]]
4
[10,20,30]
최첨단 드론 배송 시스템은 n개의 물류 허브와, 각 허브를 잇는 양방향 항로 routes 정보로 구성됩니다. 각 항로는 [허브1, 허브2, 비행 거리]를 담고 있습니다.
하나의 타겟 허브 t가 고정된 상태에서, 드론이 따라야 할 비행 로그(logs)가 주어집니다. 이 logs는 드론이 이동할 항로의 비행 거리를 순서대로 담고 있는 절대적인 비행 계획입니다.
주어진 logs를 만족하는 모든 출발점을 찾아, 각 출발점에서 시작된 전체 배송 경로를 배열 형태로 반환하는 solution 함수를 완성하세요. 이때 타겟 t는 경로 규칙을 판단하기 위한 기준점으로만 사용되며, 실제 경로가 t를 방문하지 않아도 무방합니다. 각 경로는 거쳐간 허브 번호의 순서로 된 배열([출발 허브, ...])이어야 하며, 최종 결과는 출발 허브 번호를 기준으로 오름차순 정렬해야 합니다.
드론이 허브 a에서 b로, 비행 거리 w인 항로를 통과할 때 기록은 다음과 같이 남습니다.
w (양수)로 기록된 경우: 현재 비행한 항로(a, b)가, 현재 위치 a에서 최종 목적지 t까지 가는 최단 배송 경로 상에 포함될 때
-w (음수)로 기록된 경우: 현재 비행한 항로(a, b)가, 현재 위치 a에서 최종 목적지 t까지 가는 최단 배송 경로 상에 포함되지 않을 때
물류 허브의 수 n: 2 이상 500 이하
항로 정보 routes: [허브1, 허브2, 비행 거리] 형식의 2차원 배열
비행 거리: 1 이상의 정수
하나의 허브에 연결된 모든 항로의 비행 거리는 서로 다릅니다.
로그 logs: 길이가 1 이상 500 이하인, 0이 아닌 정수 배열
주어진 입력에 대해 유효한 경로는 반드시 하나 이상 존재합니다.
예시 1:
입력:
n = 6
routes = [[1,2,4], [1,3,1], [1,5,2], [1,6,3], [2,3,2], [2,5,1], [4,5,3], [4,6,1], [5,6,4]]
target = 1
logs = [1, -4, 2]
출력: [[3,1,2,3], [4,6,5,1]]
설명:
출발점: 3 (경로 3→1→2→3)
+1: 허브 3에서 w가 1인 항로는 3→1 입니다. dist(3,1) == 1 + dist(1,1) 이므로 최단경로가 맞습니다.
-4: 허브 1에서 w가 4인 항로는 1→2 입니다. dist(1,1) < 4 + dist(2,1) 이므로 최단경로 아닙니다.
+2: 허브 2에서 w가 2인 항로는 2→3 입니다. dist(2,1) == 2 + dist(3,1) 이므로 최단경로가 맞습니다.
출발점:4 (경로 4→6→5→1)
+1: 허브 4에서 w가 1인 항로는 4→6 입니다. dist(4,1) == 1 + dist(6,1) 이므로 최단경로가 맞습니다.
4: 허브 6에서 w가 4인 항로는 6→5 입니다. dist(6,1) < 4 + dist(5,1) 이므로 최단경로가 아닙니다.
+2: 허브 5에서 w가 2인 항로는 5→1 입니다. dist(5,1) == 2 + dist(1,1) 이므로 최단경로가 맞습니다.
예시 2:
입력:
n = 4
routes = [[1,2,10], [2,3,20], [3,4,30]]
target = 4
logs = [10, 20, 30]
출력: [[1, 2, 3, 4]]
설명:
로그가 [10, 20, 30]으로 모두 양수입니다. 이는 모든 이동이 현재 위치에서 타겟(4)까지 가는 최단 경로임을 의미합니다.
1번 허브에서 출발: 1 -> 2 (비행 거리 10)는 1에서 4로 가는 최단 경로의 일부입니다.
2번 허브에서: 2 -> 3 (비행 거리 20)는 2에서 4로 가는 최단 경로의 일부입니다.
3번 허브에서: 3 -> 4 (비행 거리 30)는 3에서 4로 가는 최단 경로의 일부입니다.
따라서 [1, 2, 3, 4] 경로가 조건을 만족합니다.
예시 3:
입력:
n = 4
routes = [[1,2,1], [1,3,10], [2,4,100], [3,4,1]]
target = 4
logs = [-1, -100]
출력: [[1, 2, 4]]
설명:
로그가 [-1, -100]으로 모두 음수입니다. 이는 모든 이동이 현재 위치에서 타겟(4)까지 가는 최단 경로가 아닌, 우회 경로임을 의미합니다.
1번 허브에서 출발: 비행 거리가 1인 1 -> 2 경로로 이동합니다. 1에서 4로 가는 최단 경로는 1 -> 3 -> 4 (총 11)이므로, 1 -> 2는 최단 경로가 아닙니다. (로그 -1 만족)
2번 허브에서: 비행 거리가 100인 2 -> 4 경로로 이동합니다. 2에서 4로 가는 최단 경로는 2 -> 1 -> 3 -> 4 (총 12)이므로, 2 -> 4는 최단 경로가 아닙니다. (로그 -100 만족)
따라서 [1, 2, 4] 경로가 조건을 만족합니다.
4
[[1,2,10],[2,3,20],[3,4,30]]
4
[10,20,30]