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

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

1916번: 최소비용 구하기

 

이번에 드디어 다익스트라 알고리즘을 배워서 실제 문제 풀이에 적용하였다.

알고리즘 문제해결 전략에 나와있는 것을 응용하여 해결했다.

 

1. 준비작업

 1-1. vector<pair<int,int>> adj_list[100001]

 먼저 각 노드들의 인접리스트를 만들 이차원 백터 vector<pair<int,int>> adj_list[100001]을 선언해주었다.

이 백터의 역할은 a번째 노드와 연결되어 있는 b번째 노드까지의 거리를 저장해둔 값으로 

adj_list[x].push_back(make_pair(y,z))에서 x는 a번째 노드, y는 b번째노드, z는 거리로 이것들을 인접리스트로 선언하여 언제 priority_queue에 넣을지 도움을 주는 역할을 한다.

 

1-2. prioity_queue

 이 문제에서 가장 중요한 것은 노드들을 잇는 간선들의 쌍을 저장하는 방법인데 이때 쓴 방법이 바로 prioity_queue였다. 그냥 queue와 다르게 prioity_queue는 heap을 유지하면서 내림차순으로 queue를 유지시키기 때문에 queue에 push만 해주면 알아서 자동으로 정렬이 가능하다. 자세한 내용은 아래 글을 참고하면 된다!

 

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

[C/C++] 백준 11286: 절댓값 힙 (구조체와 연산자 오버로딩)

 

 

 그래서 이 문제에서도 priority_queue를 priority_queue<pair<int,int>> p1으로 선언해주었다. 이때 자체적으로 비교하여 정렬을 유지할 때 pair의 첫번째 원소부터 먼저 비교하기 때문에 첫번째 원소를 정점까지의 거리로, 두번째 원소를 정점의 번호로 구성하였다. 위에서 언급했다싶이 priority_queue는 기본적으로 가장 큰 원소가 위로 가도록 큐를 구성하기 때문에 거리의 부호를 바꿔서 거리가 작은 정점부터 꺼내지도록 구현하였다. 즉, 아래와 같이

 

p1.push(make_pair(-nextDist,tmp))

 

에서 p1에 push를 할때 거리의 값을 음수로 선언하고 아래와 같이

 

int cur_dist=-p1.top().first;

 

p1의 첫번째 값을 불러올때 다시 -를 붙여 그 값을 원상복귀하여 계산하였다.

이렇게 한 이유는 부호를 바꿔서 넣어주지 않으면 복잡하게 우선순위를 선언해야하기 때문이다.

 

 

3. dist[]

 마지막으로 시작 노드에서의 최단거리를 저장해주는 배열 dist[]를 선언해주었다.

 

 vector<int>dist(V+1,INT_MAX)

 

와 같은 형식으로 선언해주었으며 이 배열을 통해 우리가 찾는 최단거리인지 아닌지를 판별해주기 때문에 주의해야한다.

 

 

2. 본격 구현

 가장 기본적인 생각은 priority_queue를 이용해 while문 내에서 현재까지 만든 노선중에서 가장 거리가 가까운 노드를 찾아내고 (p1.top()), 그 값을 삭제시키는 것이다 (p1.pop()). 이 작업은 p1의 아무것도 남아있지 않을 때까지 계속된다. 

 현재 정점까지의 최단거리를 int cur_dist=-p1.top().first 로,

현재 정점의 번호를 int cur_V=p1.top().second;으로 저장한 뒤 현재 정점을 priority_queue에서 삭제시킨다.

 

 그리고 여기서 가장 중요한 조건문이 나온다. 바로!!

 

if(dist[cur_V]<cur_dist) continue; 

 

예를 들어 이미 우선순위 큐에 (12,c)가 있는 상태에서 새로운 노선 (8,c)가 들어온다면 dist[c]를 갱신하려고 한다고 가정해보자. 이 같은 경우에 두 가지 방법으로 해결할 수 있는데

 

1. 우선순위 큐 내에서 (12,c)를 찾아내 (8,c)로 바꾸는 것이고

2. (12,c)를 그대로 두고 (9,c)를 추가한 뒤, 나중에 큐에서 (12,c)가 꺼내지면 무시하는 방법이 있다.

 

 일단 일반적인 해결방법은 2번째 방법이다! 첫번째 방법은 C++ 표준 라이브러리에서 1번의 연산을 지원하지 않아 직접 구현하기에 복잡하기 때문이다.

 2번째 방법은 위에서 언급한 조건문을 통해 해결이 가능한데 이미 c까지 가는 노드의 최단거리보다 큰 거리가 cur_dist로 올 경우 이 경우는 무시하고 그 다음 queue.top을 확인하게 된다.

 

만약 이 조건을 통과했다면 현재 노드와 연결된 노드들을 다 비교해가며 인접한 노드들까지의 거리가 최단거리가 된다면 dist[]배열을 업데이트 해주고 priority_queue에 push해준다.(for문!!)

 

이 방법을 통해 다익스트라 알고리즘을 구현할 수 있다!

 

 

3. 소스코드

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

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

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

vector<int> dijkstra(int start)
{
  
  vector<int>dist(V+1,INT_MAX);
  dist[start]=0;  
  p1.push(make_pair(0,start));
  while(!p1.empty()){
    int cur_dist=-p1.top().first; //정점까지의 거리 중 최단거리, -인 수를 복원
    int cur_V=p1.top().second; //정점의 번호
    //cout<<"이번에 나올 수는:"<<p1.top().second<<"\n";
    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));
    }
  
  int start,end;
  cin>>start>>end;
  vector<int> dist;
  dist=dijkstra(start);
  cout<<dist[end];
  
}

 

BOJ 1753: 최단경로

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

1753번: 최단경로

 

 

구현!

이와 비슷한 문제인 BOJ 1753: 최단경로도 코드를 조금만 변형시켜 문제를 풀 수 있다. adj_list의 범위를 늘리고 dijsktra 함수는 바꿀 필요가 없다. 단지 출력할 때 초기값 그대로 남아있다면 INF를 출력하도록 했다.

 

 위에서 언급했던 2. (12,c)를 그대로 두고 (9,c)를 추가한 뒤, 나중에 큐에서 (12,c)가 꺼내지면 무시하는 방법이 여기서 힘을 발휘한다. 이 문제에서는 서로 다른 두 정점 사이에 여러개의 간선이 존재할 수 있지만 어차피 이 구현 방식이라면 가장 짧은 거리 하나만 계산하고 나머지는 다 조건문으로 걸러지게 된다.

 

소스코드

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

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

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

vector<int> dijkstra(int start)
{
  
  vector<int>dist(V+1,INT_MAX);
  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 start;
  cin>>V>>E>>start;
  for(int i=0;i<E;i++)
    {
      int tmp1,tmp2,w;
      cin>>tmp1>>tmp2>>w;
      adj_list[tmp1].push_back(make_pair(tmp2,w));
    }
  
  vector<int> dist;
  dist=dijkstra(start);
  for(int i=1;i<dist.size();i++)
    {
      if(dist[i]==INT_MAX)
        cout<<"INF"<<"\n";
      else
        cout<<dist[i]<<"\n";
    } 
  
}

 

 

BOJ 11779 최소비용 구하기 2

 

이 문제는 위에 나와있는 최소비용 구하기에 경로만을 출력하면 된다.

이것을 구현하기 위해서 cpy_once[100001]을 만들어 경로를 저장해두었는데 A에서 B로 갔을 경우

cpy_once[B]=A로 저장해두었다.

왜냐하면 A에서 다른 곳으로 가는 경우는 여러가지일 수 있지만 B로 오는 노드는 A 하나 뿐이기 때문이다.

이를 마지막에 역추적하여 배열을 저장하면 원하는 답을 구할 수 있다!!

 

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

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

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

vector<int> dijkstra(int start)
{
  
  vector<int>dist(V+1,INT_MAX);
  dist[start]=0;  
  p1.push(make_tuple(0,start,0));
  while(!p1.empty()){
    int cur_dist=-get<0>(p1.top()); //정점까지의 거리 중 최단거리, -인 수를 복원
    int cur_V=get<1>(p1.top()); //정점의 번호
    city_route.push_back(cur_V);
    
    //cout<<"이번에 나올 수는:"<<p1.top().second<<"\n";
    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_tuple(-nextDist,tmp,cur_V)); //음수로 바꿔야지 작은 수부터 출력 가능함
        cpy_once[tmp]=cur_V;
      }
    }
  }
  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));
    }
  
  int start,end;
  cin>>start>>end;
  vector<int> dist;
  dist=dijkstra(start);
  int cities=0,tmp1=end;
  vector<int>arr;
  while(1){
    if(tmp1==0){
      break;
    }    
    arr.push_back(tmp1);
    tmp1=cpy_once[tmp1];
    cities++;
  }
  cout<<dist[end]<<"\n"<<cities<<"\n";
  for(int i=cities-1;i>=0;i--){
    cout<<arr[i]<<" ";
  }
  
}