거점
문제
한 학생은 초기에 1번 지점의 위치에 서 있으며, N번 지점으로 이동하고자 한다. 이때 시작 지점인 1번 지점에서 출발하여 도착 지점인 N번 지점에 최대한 빠르게 도착하는 것이 목표다. 임의의 두 노드(지점) 사이에는 통로가 존재할 수 있는데, 각 통로마다 1 이상 10 이하의 값을 가지는 통로의 길이 정보가 함께 주어진다. 예를 들어 통로의 길이가 5인 경우, 해당 통로를 이용하여 이동하는 경우 5만큼의 거리를 이동해야 하는 것으로 이해할 수 있다. 두 개의 노드를 잇는 통로는 여러 개 일 수 있다.
총 노드의 개수 N은 최대 8,000의 값을 가지며, 통로의 개수 M은 최대 100,000의 값을 가진다. 또한 통로는 양방향 통로라서 A와 B를 연결하는 통로가 존재한다면 A에서 B로도 갈 수 있고, B에서 A로도 갈 수 있다.
이때, 항상 3개의 거점을 거쳐야 한다. 주어지는 3개의 거점의 번호는 항상 1번과 N번에 해당하지 않는다. 또한 3개의 거점 번호는 항상 서로 다르다. 구체적으로 학생은 3개의 거점을 최소 1번씩은 방문하는 조건을 만족하며 1번 노드에서 N번 노드까지 최단 경로로 이동해야 한다. 결과적으로 1번 노드에서 N번 노드로 이동하기 위한 최단 거리를 계산하는 프로그램을 작성하여라. 만약 1번 노드에서 3개의 거점을 거쳐서 N번 노드에 도달이 불가능한 경우 -1을 반환하여라.
한 예시로 N=7, M=10, 그리고 거쳐야 하는 거점 노드가 2번, 3번, 4번인 상황을 가정해보자. 이 경우 1번 노드에서 7번 노드까지 도달하는 과정에서 2번, 3번, 4번 노드에 대하여 각각 한 번씩은 방문해야 하는 것이다. 현재 예시에서의 모든 노드와 모든 통로(간선)를 아래 그림과 같이 표현하였다. 그림에서 통로에 적힌 수는 해당 통로의 길이를 의미한다. 더불어 아래 그림에서 거쳐야 하는 거점 노드는 빨간색으로 음영 처리 하였으며, 출발 노드인 1번과 도착 노드인 N번 노드는 파란색으로 음영 처리를 하였다.
> (원본 문서의 그래프 그림이 텍스트 추출 과정에서 유실되었다. 간선 정보는 입출력 예시의 edges 배열과 같다.)
이 경우, 1번 → 4번 → 2번 → 3번 → 7번 순서대로 이동하면 총 이동 거리가 23(7 + 5 + 6 + 5)이 되며, 이 값은 문제의 요구 사항을 만족하는 최단 거리에 해당한다.
> (원본 문서의 그래프 그림이 텍스트 추출 과정에서 유실되었다.)
주어진 3개의 지점을 반드시 거쳐서 1번에서 N번 노드까지 가기 위한 최단 거리를 계산하는 프로그램을 작성하여라. 입력으로 주어지는 데이터에서 항상 N은 5 이상의 값을 가진다. 그리고 3개의 거점 노드는 서로 겹치지 않으며, 1번 노드와 N번 노드에 해당하지 않는다.
또한 학생이 이동하는 과정에서 한 노드를 여러 번 방문할 수 있고, 한 통로를 여러 번 지나갈 수 있다. 학생은 항상 최단 경로로 이동해야 하며 시작 노드는 반드시 1번이고, 마지막 노드는 반드시 N번이어야 한다.
입출력 예시
예시 1
입력
7, 10, [[1, 2, 8], [1, 4, 7], [2, 3, 6], [2, 4, 5], [3, 5, 8], [3, 7, 5], [4, 5, 9], [4, 6, 8], [5, 6, 2], [6, 7, 8]], [2, 3, 4]
출력
23
예시 2
입력
5, 7, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [2, 4, 2], [3, 4, 1], [3, 5, 5], [4, 5, 2]], [2, 3, 4]
출력
5
예시 3
입력
5, 5, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [3, 5, 5], [4, 5, 2]], [2, 3, 4]
출력
11
예시 4
입력
5, 5, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [2, 4, 2], [3, 5, 5]], [2, 3, 4]
출력
11
예시 5
입력
5, 4, [[1, 2, 1], [1, 3, 3], [2, 4, 2], [3, 5, 5]], [2, 3, 4]
출력
14
예시 6
입력
5, 4, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [3, 5, 5]], [2, 3, 4]
출력
-1
예시 7
입력
5, 4, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [2, 4, 2]], [2, 3, 4]
출력
-1
입력 조건
가장 먼저 노드의 개수 N이 주어진다. N의 값은 5 이상 8,000 이하의 자연수다.
이어서 통로의 개수 M이 주어진다. M의 값은 최대 100,000 이하의 자연수다. 통로는 양방향 통로를 의미한다. 따라서, A와 B가 연결되어 있다면 A에서 B로도 갈 수 있으며 B에서 A로도 갈 수 있다.
이어서 각 통로에 대한 정보가 담긴 2차원 배열 edges가 주어진다. 구체적으로 M×3 형태의 배열로 주어지는데, 각 통로에 대한 정보는 A, B, K로 구성된다. 이는 A와 B가 연결되어 있다는 의미이며, K는 A와 B를 연결하는 통로의 길이(통로를 거쳐 이동하기 위한 거리)를 의미한다. A와 B는 서로 다른 노드이며, 통로의 길이는 1 이상 10 이하의 자연수로 주어진다.
이어서 거점 노드의 정보가 담긴 1차원 배열 points가 주어진다. 구체적으로 3개의 원소를 갖는 1차원 배열로 [X, Y, Z] 형태를 가진다. 세 개의 각 원소의 값은 1 초과 N 미만의 자연수로, 서로 다른 값을 가진다.
출력 조건
1번에서 출발하여 주어진 3개의 거점을 한 번씩은 방문하고 N번 노드에 도착하기 위한 최단 거리를 자연수 형태로 반환한다. 만약 1번 노드에서 3개의 거점을 거쳐 N번 노드에 도달이 불가능한 경우 -1을 반환한다.
요구사항
- solution(N, M, edges, points) 함수를 만들고 답을 반환해야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
- 케이스는 23개이고, 그 가운데 8개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 23개를 전부 통과해야 해결입니다.
예시
공개 케이스 8개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 23개를 전부 통과해야 해결입니다.
7, 10, [[1, 2, 8], [1, 4, 7], [2, 3, 6], [2, 4, 5], [3, 5, 8], [3, 7, 5], [4, 5, 9], [4, 6, 8], [5, 6, 2], [6, 7, 8]], [2, 3, 4]
23
5, 7, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [2, 4, 2], [3, 4, 1], [3, 5, 5], [4, 5, 2]], [2, 3, 4]
5
5, 5, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [3, 5, 5], [4, 5, 2]], [2, 3, 4]
11
5, 5, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [2, 4, 2], [3, 5, 5]], [2, 3, 4]
11
5, 4, [[1, 2, 1], [1, 3, 3], [2, 4, 2], [3, 5, 5]], [2, 3, 4]
14
5, 4, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [3, 5, 5]], [2, 3, 4]
-1
5, 4, [[1, 2, 1], [1, 3, 3], [2, 3, 1], [2, 4, 2]], [2, 3, 4]
-1
16, 3085, [[15, 6, 3], [1, 5, 4], [15, 16, 3], [15, 9, 10], [9, 10, 3], [14, 12, 2], [7, 1, 10], [12, 15, 6], [16, 2, 1], [9, 13, 2], [8, 14, 10], [9, 15, 2], [14, 3, 1], [10, 3, 2], [5, 16, 5], [12, 11, 4], [3, 7, 10], [10, 9, 1], [13, 3, 2], [5, 6, 2], [4, 9, 2], [4, 10, 10], [2, 15, 8], [2, 13, 4], [11, 15, 10], [9, 1, 1], [6, 12, 5], [14, 9, 3], [4, 15, 1], [13, 4, 1], [4, 3, 1], [12, 16, 9], [7, 2, 7], [2, 3, 7], [5, 13, 2], [9, 2, 9], [3, 2, 2], [1, 8, 7], [1, 10, 4], [16, 6, 2], [2, 6, 4], [14, 6, 10], [3, 16, 10], [12, 14, 8], [2, 6, 2], [9, 5, 1], [8, 12, 7], [2, 3, 9], [16, 6, 2], [12, 5, 6], [11, 2, 2], [12, 6, 5], [1, 15, 4], [13, 1, 4], [13, 1, 9], [3, 11, 6], [6, 16, 7], [6, 8, 2], [4, 11, 4], [7, 8, 6], [4, 9, 10], [5, 6, 8], [9, 8, 8], [1, 13, 2], [4, 11, 4], [1, 10, 3], [3, 4, 5], [2, 8, 1], [6, 9, 8], [8, 5, 3], [10, 13, 9], [14, 13, 6], [4, 16, 2], [15, 4, 5], [2, 13, 5], [13, 5, 9], [9, 13, 8], [8, 5, 1], [16, 10, 10], [7, 15, 5], [1, 15, 10], [4, 3, 7], [9, 12, 10], [16, 1, 9], [9, 15, 3], [9, 16, 3], [7, 9, 4], [15, 14, 6], [1, 6, 5], [15, 4, 7], [12, 7, 7], [9, 13, 1], [4, 14, 3], [12, 3, 6], [3, 10, 4], [5, 13, 7], [14, 2, 6], [9, 12, 6], [8, 2, 1], [4, 9, 5 ... 여기까지만 보여 드립니다 (전체 36,958자)
4
참고 사항
풀이에 도움이 되는 배경입니다. 지켜야 하는 규격은 위의 입출력 조건과 요구사항에 있습니다.
원본에서 모의고사 9회 3번입니다.
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 8개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.