특정한 최단 경로_다엑스트라_백준_1504

-문제-

 

-문제 접근-

이 문제는 N번의 정점으로 가는 최단 경로에서 주어진 두 지정 정점(v1, v2)를 거쳐야되는 조건이 들어 있는 문제로

두 지정 정점을 지나는 최단 거리를 구하는 문제입니다.

 

조건:

• 그래프는 방향성이 없는 (양방향) 가중치 그래프입니다.
• 한 번 방문한 정점이나 간선을 다시 방문할 수 있으며 전체 경로는 최단 경로여야 합니다.

문제의 조건에 따른 경로의 경우

 

• 경우 1: 1 → v1 → v2 → N
• 경우 2: 1 → v2 → v1 → N

두 경로 중 더 짧은 경로의 거리를 구하면 된다는 것을 알 수 있습니다.

 

접근 방식:

인접 리스트

• 각 정점을 배열의 인덱스로 관리하고, 각 정점에 연결된 간선들을 구조체(Edge)를 사용하여 저장합니다.

다익스트라

• 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하며 우선순위 큐를 사용하여 현재까지 발견된 가장 짧은 경로를 가진 정점을 선택하고, 인접 정점의 거리를 갱신합니다.

 

위 문제에서는 다익스트라를 3번 실행을 합니다.(모든 정점)

• 1번 정점에서 출발
• v1에서 출발
• v2에서 출발

경로 경우의 수

• 경우 1: 1 → v1 → v2 → N
• 경우 2: 1 → v2 → v1 → N

-코드-

 

 

-코드 설명-

 

numeric_limits<int>::max():

최단 거리 계산에 문제가 생기지 않도록 INF로 초기화

 

greater<pair<int,int>> 사용:
우선순위 큐가 최소 힙처럼 동작하도록 만들어, 작은 값이 우선 순위를 가지도록 합니다.

 

그래프 구성:

• Graph graph(N+1);을 통해 1번부터 N번 정점을 사용할 수 있도록 인접 리스트를 구성합니다.
• 각 간선에 대해 양방향으로 정보를 저장합니다.

최단거리 계산:

• 다익스트라 1: 1번 정점에서 모든 정점까지의 최단 거리 → distFrom1
• 다익스트라 2: v1에서 모든 정점까지의 최단 거리 → distFromV1
• 다익스트라 3: v2에서 모든 정점까지의 최단 거리 → distFromV2

이후,

• 경우 1: distFrom1[v1] + distFromV1[v2] + distFromV2[N]
• 경우 2: distFrom1[v2] + distFromV2[v1] + distFromV1[N]

 

 

-END-