[백준] No.13308 - 주유소 (C++, 다익스트라)

문제

 

www.acmicpc.net/problem/13308

13308번: 주유소

 

풀이

 

solved.ac 난이도: Gold 1

 

또다시 다이나믹 프로그래밍을 적용하여 해결하는 다익스트라 문제.

 

최단 거리을 저장하는 2차원 배열 dist[city_idx][oil_cost]은 다음의 값을 저장한다.

1번 도시에서 city_idx도시까지의 경로 중 가장 싼 기름 가격이 oil_cost일 때의 최소 비용(최단 거리* 기름 가격)

 

이를 위해 우선순위 큐에는 3가지 값을 저장하는 구조체를 저장시킨다.

1. cost: 지금까지의 비용 

2. idx: 현재 도시의 번호

3. min_oil: 지금까지 지나온 도시 중에 가장 싼 기름 값

 

struct OilStation{
  ll cost;
  int idx;
  int min_oil;
 
  bool operator<(const OilStation& x) const{
    return cost > x.cost;
  }
};

 

min_oil(가장 싼 기름값)을 저장하는 이유는 현재 도시로부터 다른 도시로 나아갈때 필요한 기름을

지금까지 지나온 도시 중 기름 가격이 가장 싼곳에서 미리 넣어온다고 계산해야 하기 때문이다.

어떠한 경우에도 비싼 도시보단 싼 곳에서 기름을 넣는것이 항상 이득이다.

 

따라서 다음 도시까지의 비용인 next_cost 계산은 

next_cost = cost * (다음 도시로의 거리 * min_oil)이 된다.

 

그리고 다음 도시의 기름 값이 더 싸다면 우선순위 큐에 삽입할 새로운 구조체에는 더 싼 기름 값을 저장해 주자.

 

ll Dijkstra(int start){
  priority_queue<OilStation> pq;
  ll dist[2501][2501];
  memset(dist, 0x7f, sizeof(dist));
 
  pq.push({0, start, oil_cost[start]});
  dist[start][oil_cost[start]] = 0;
 
  int now_city, next_city, min_oil;
  ll cost, next_cost;
  while(!pq.empty()){
    now_city = pq.top().idx;
    cost = pq.top().cost;
    min_oil = pq.top().min_oil;
    pq.pop();
 
    if(dist[now_city][min_oil] < cost)
      continue;
 
    for(int i=0; i<adj[now_city].size() ; ++i){
      next_city = adj[now_city][i].second;
      next_cost = cost + (ll)adj[now_city][i].first * min_oil ; 
      //지금까지 지나온 도시 중 기름 가격이 가장 싼곳에서 미리 넣어온다고 생각(항상 이득이기 때문에)
 
      int next_oil = min(min_oil , oil_cost[next_city]);
      //다음 도시의 가격이 더 작다면 업데이트
      if( next_cost < dist[next_city][next_oil]){
        pq.push({next_cost, next_city, next_oil});
        dist[next_city][next_oil] = next_cost;
      }
    }
  }
    
  ll answer = MAXCOST;
  for(int i=1; i<=2500 ; ++i)
    answer = min(answer, dist[city_num][i]);
  
  return answer;
} 

 

 

이러한 풀이가 왜 항상 최소 비용을 구할 수 있는지 생각해보자.

일반적인 다익스트라 문제에서는 최단 경로는 일차원 배열을 이용해 구하게 된다.

4번 도시까지의 최단 거리(dist[4])는 1->3->4의 거리인 7이 최소가 된다.

하지만 2차원 배열 dist[city_idx][oil_cost]에서는 모든 oil_cost에서의 최단 경로를 찾아보게 된다.

 

dist[4][2]에서의 최단 경로(최단 비용을 만드는 경로)는 기름 가격이 2인 2번 도시를 최단 경로로 방문한 후, 

2번 도시에서 목적지인 4번 도시까지의 최단 경로를 가게 된다.

 

하지만 dist[4][4]인 경우 기름 가격이 4인 3번 도시를 최단 경로로 방문한 후 4번 도시로 최단 경로로 간다.

 

즉, 2차원 배열을 통해 1번 도시에서 city_idx도시까지의 경로 중 가장 싼 기름 가격이 oil_cost일 때의 최소 비용을 모두 구할 수 있다.

 

 

 

비슷한 문제로는 [백준] 도로포장(1162)도 있으니 해결해보자.

 

 

코드

 

	#include<iostream>
	#include<queue>
	#include<vector>
	#include<string.h>
	using namespace std;
	typedef long long ll;
	const ll MAXCOST = INT64_MAX;
	int city_num, road_num;
	vector<vector<pair<int,int>>> adj;
	int oil_cost[2501];
	struct OilStation{
	ll cost;
	int idx;
	int min_oil;
	bool operator<(const OilStation& x) const{
	return cost > x.cost;
	}
	};
	ll Dijkstra(int start){
	priority_queue<OilStation> pq;
	ll dist[2501][2501];
	memset(dist, 0x7f, sizeof(dist));
	pq.push({0, start, oil_cost[start]});
	dist[start][oil_cost[start]] = 0;
	int now_city, next_city, min_oil;
	ll cost, next_cost;
	while(!pq.empty()){
	now_city = pq.top().idx;
	cost = pq.top().cost;
	min_oil = pq.top().min_oil;
	pq.pop();
	if(dist[now_city][min_oil] < cost)
	continue;
	for(int i=0; i<adj[now_city].size() ; ++i){
	next_city = adj[now_city][i].second;
	next_cost = cost + (ll)adj[now_city][i].first * min_oil ;
	//지금까지 지나온 도시 중 기름 가격이 가장 싼곳에서 미리 넣어온다고 생각(항상 이득이기 때문에)
	int next_oil = min(min_oil , oil_cost[next_city]);
	//다음 도시의 가격이 더 작다면 업데이트
	if( next_cost < dist[next_city][next_oil]){
	pq.push({next_cost, next_city, next_oil});
	dist[next_city][next_oil] = next_cost;
	}
	}
	}
	ll answer = MAXCOST;
	for(int i=1; i<=2500 ; ++i)
	answer = min(answer, dist[city_num][i]);
	return answer;
	}
	int main(){
	ios_base::sync_with_stdio(0);
	cin>>city_num>>road_num;
	adj = vector<vector<pair<int,int>>>(city_num+1);
	for(int i=1; i<=city_num ; ++i)
	cin>>oil_cost[i];
	int u, v, cost;
	for(int i=0; i<road_num ; ++i){
	cin>>u>>v>>cost;
	adj[u].push_back(make_pair(cost, v));
	adj[v].push_back(make_pair(cost, u));
	}
	cout<<Dijkstra(1)<<'\n';
	return 0;
	}

view raw [BaekJoon]_13308_주유소.cpp hosted with ❤ by GitHub