본문 바로가기
알고리즘!/Dynamic Programming

[C/C++] 백준 1504: 특정한 최단 경로 (다익스트라 풀이)

by soeayun 2023. 9. 30.

https://www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

 

풀이!!!

다익스트라 알고리즘!

 다익스트라를 제대로 구현을 한 상태라면 사실 쉽게 풀 수도 있다. 다익스트라를 4번에서 6번 사용을 한다면 최단거리를 1부터 N까지 V1과 V2를 거치면서 최단거리를 구하면 된다.

  이 문제에서 한번 이동했던 정점을 다시 이동할 수 있다는 것은 다익스트라를 여러번 사용할 때 같은 정점을 지나도 된다는 것이지 한번의 다익스트라 안에서 최단거리를 구할 때 같은 정점을 지나는 여러번 지나는 것이 아니다. 사실 V1에서 V2로 가는 최단경로를 갈때 임의의 노드를 두번 거치게 된다면 최단거리가 되지 않을 것이다.

 일단 다익스트라 알고리즘을 제대로 구현해야하는데 아래의 포스팅을 보면 도움이 될 것이다!!

https://donggul-godsang.tistory.com/77

 

[C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!)

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다

donggul-godsang.tistory.com

 

 

 

문제 알고리즘!!

 사실 Vstart-> V1-> V2- >Vend 까지 가는 거리와 Vstart-> V2-> V1-> Vend까지의 거리 중에 최솟값을 구하면 된다. 난 6번의 다익스트라를 사용했는데 Vstart-> V1, V1->V2, V2-> Vend 총 3번과, Vstart->V2, V2-> V1, V1-> Vend 3번으로 총 6번 다익스트라를 이용하여 각각의 거리 더하면 된다. 

 다만 여기서 한가지 주의해야할 점은 경로가 없을 때는 -1을 출력해야하기 때문에 만약 Vtmp1-> Vtmp2로 가는 경우가 없을 때, 즉 dist배열이 INT_MAX일 때 -1을 출력하고 return하면 된다!

 

 다익스트라를 4번만 사용하는 방법은 아래 포스팅을 참고하면 된다!

https://yabmoons.tistory.com/386

 

[ 백준 1504 ] 특정한 최단 경로 (C++)

백준의 특정한 최단 경로(1504) 문제이다.[ 문제 바로가기 ] [ 문제풀이 ]1번 정점에서 N번 정점으로 최단 거리로 이동하려고 하는데, 반드시 거쳐야 하는 2개의 정점을 거쳐서 갈 때의 최단 거리를

yabmoons.tistory.com

 

그리고 참고로 노드로 구성되어 있는 그래프를 확인하고 싶을 때는 아래 사이트를 가서 예제를 입력하면 한눈에 확인할 수 있어 문제를 푸는데 큰 도움이 되니 참고하면 좋을 것 같다!!!

https://csacademy.com/app/graph_editor/

 

CS Academy

 

csacademy.com

 

 

소스코드!!

 

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

int V;
vector<pair<int,int>> adj_list[801]; //각 노드들의 인접 리스트를 만듦
int visit_once[801];
priority_queue<pair<int,int>> p1; //priority queue를 이용하여 각 순간마다 최단거리에 있는 노드부터 연산 시작
 // 각 노드까지의 최단거리를 저장

vector<int> dijkstra(int start)
{  
  vector<int>dist(V+1,INT_MAX);
  memset(visit_once,0,801*sizeof(int));
  dist[start]=0;  
  p1.push(make_pair(0,start));
  
  while(!p1.empty()){
    int cur_dist=-p1.top().first; //정점까지의 거리 중 최단거리, -인 수를 복원
    int cur_V=p1.top().second; //정점의 번호
    p1.pop();
    if(dist[cur_V]<cur_dist) // 지금 꺼낸 것보다 더 짧은 경로가 이미 있다면 지금 꺼낸 것을 무시한다
      continue; 

    for(int i=0;i<adj_list[cur_V].size();i++){
      int tmp=adj_list[cur_V][i].first; //인접한 노드들의 정점
      int nextDist=cur_dist+adj_list[cur_V][i].second; //첫 노드에서 인접한 노드까지의 거리
      if(dist[tmp]>nextDist) //더 짧은 경로를 발견하면 tmp까지의 최단거리를 갱신하고 queue에 넣어줌
      {
        dist[tmp]=nextDist;
        p1.push(make_pair(-nextDist,tmp)); //음수로 바꿔야지 작은 수부터 출력 가능함
      }
    }
  }
  return dist;
}

int main() {    
  int bus;
  cin>>V>>bus;
  for(int i=0;i<bus;i++)
    {
      int city1,city2,price;
      cin>>city1>>city2>>price;
      adj_list[city1].push_back(make_pair(city2,price));
      adj_list[city2].push_back(make_pair(city1,price));
    }
  int mid1,mid2,result=0;
  cin>>mid1>>mid2;
  
  int start=1,end=V,min_value1,min_value2;

  vector<int> dist;
  dist=dijkstra(start); // 시작점부터 v1
  if(dist[mid1]==INT_MAX)
  {
    cout<<-1;
    return 0;
  }
  min_value1=dist[mid1];
  
  dist=dijkstra(mid1); // v1부터 v2까지
  if(dist[mid2]==INT_MAX){
    cout<<-1;
    return 0;
  }
  min_value1+=dist[mid2];
   
  dist=dijkstra(mid2); //v2부터 마지막까지
  if(dist[end]==INT_MAX)
  {
    cout<<-1;
    return 0;
  }
  min_value1+=dist[end];
  

  dist=dijkstra(start); // 시작점부터 v2
  if(dist[mid2]==INT_MAX)
  {
    cout<<-1;
    return 0;
  }
  min_value2=dist[mid2];
  
  dist=dijkstra(mid2); // v2부터 v1까지
  if(dist[mid1]==INT_MAX){
    cout<<-1;
    return 0;
  }
  min_value2+=dist[mid1];
   
  dist=dijkstra(mid1); //v1부터 마지막까지
  if(dist[end]==INT_MAX)
  {
    cout<<-1;
    return 0;
  }
  min_value2+=dist[end];
  
  result=min(min_value1,min_value2);  
  cout<<result; 
  
}