[대표 유형] 다익스트라 최단 경로 추적 1

문제 설명

임의의 단방향 간선 그래프가 인접 행렬의 형태로 주어졌을 때 1 번 정점에서 n 번 정점까지의 최단 경로를 반환하는 solution 함수를 작성하시오.

단, 최단 경로에는 1 번 정점과 n 번 정점을 포함하여 반환합니다. 이때 n은 정점의 개수이며, 모든 정점은 1번 정점부터 n번 정점까지 번호가 부여됩니다.

개념 설명

다익스트라 알고리즘은 단방향 간선 그래프 중 모든 간선의 가중치가 양수인 상황에서 적용할 수 있는 One-to-All 최단 경로 알고리즘입니다.
이때 최단 경로를 구하기 위해서는 Dist 배열을 갱신하는 과정에서 갱신될 때 지나온 경로를 함께 저장하고, 다익스트라 알고리즘이 종료된 후, 해당 경로를 역추적하는 과정으로 진행됩니다.

다익스트라 알고리즘 참고

아래와 같은 단방향 그래프가 있다고 가정합니다.

이때 시작 정점을 기준으로 Dist 배열과 동시에 Path 배열을 초기화합니다.

다익스트라 알고리즘을 적용하는 과정에서 Dist를 갱신했다면 해당 갱신을 하는데 이용된 경로(정점 및 간선 정보)를 Path에 저장합니다.

이후 우선순위 큐를 활용한 다익스트라 과정을 동일하게 반복합니다.

다익스트라 알고리즘을 모두 진행하면 아래와 같은 Dist 및 Path 정보를 알 수 있습니다.

만일 1번 정점에서 시작하여 5번 정점에 도착하는 최단 경로를 구한다고 가정합니다. 이때 도착점인 5번 정점부터 시작하여 Path에 저장된 경로 정보(이전 정점 또는 간선 정보)를 바탕으로 역추적을 시작합니다.

이러한 역추적 과정을 시작 정점에 도착할 때까지 반복하여 경로를 계산합니다.

해당 경로 추적 알고리즘을 바탕으로 1번 정점에서 5번 정점에 도착하는 최단 경로는 $1 \rightarrow 3 \rightarrow 5$ 임을 알 수 있습니다.

제한 사항

• 매개변수 adjMat은 단방향 그래프의 인접행렬을 나타낸 $n \times n$ 크기의 2차원 배열입니다.
  • 정점의 개수 n은 2 이상 2,000 이하의 자연수입니다.
  • adjMat[i][j]는 i 번 정점에서 j 번 정점으로 이동하는 간선의 가중치를 의미합니다.
  • adjMat[i][j]는 0 이상 20,000 이하의 정수입니다.
  • adjMat[i][j]가 0이라면, 이는 i 번 정점에서 j 번 정점으로 이동하는 간선이 존재하지 않음을 의미합니다.
• 1 번 정점에서 n 번 정점으로 가는 최단 경로가 반드시 하나만 존재하도록 간선 정보가 주어집니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 예제 1은 위 문제 설명에서의 예시와 동일합니다. 최단 경로는 $1 \rarr 3 \rarr 5$이며 경로의 총길이는 3입니다.

2번 테스트케이스 설명

• 1 번 정점에서 5 번 정점으로 가는 경로가 $1 \rarr 3 \rarr 4 \rarr 5$로 유일하며 최단 경로입니다. 경로의 총길이는 17입니다.

3번 테스트케이스 설명

• 1 번 정점에서 6 번 정점으로 가는 최단 경로는 $1 \rarr 4 \rarr 6$이며 경로의 총길이는 6입니다.