Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
풀이
solved.ac 난이도: Gold 1
또다시 다이나믹 프로그래밍을 적용하여 해결하는 다익스트라 문제.
최단 거리을 저장하는 2차원 배열 dist[city_idx][oil_cost]은 다음의 값을 저장한다.
1번 도시에서 city_idx도시까지의 경로 중 가장 싼 기름 가격이 oil_cost일 때의 최소 비용(최단 거리* 기름 가격)
이를 위해 우선순위 큐에는 3가지 값을 저장하는 구조체를 저장시킨다.
1. cost: 지금까지의 비용
2. idx: 현재 도시의 번호
3. min_oil: 지금까지 지나온 도시 중에 가장 싼 기름 값
1
2
3
4
5
6
7
8
9
|
struct OilStation{
ll cost;
int idx;
int min_oil;
bool operator<(const OilStation& x) const{
return cost > x.cost;
}
};
|
cs |
min_oil(가장 싼 기름값)을 저장하는 이유는 현재 도시로부터 다른 도시로 나아갈때 필요한 기름을
지금까지 지나온 도시 중 기름 가격이 가장 싼곳에서 미리 넣어온다고 계산해야 하기 때문이다.
어떠한 경우에도 비싼 도시보단 싼 곳에서 기름을 넣는것이 항상 이득이다.
따라서 다음 도시까지의 비용인 next_cost 계산은
next_cost = cost * (다음 도시로의 거리 * min_oil)이 된다.
그리고 다음 도시의 기름 값이 더 싸다면 우선순위 큐에 삽입할 새로운 구조체에는 더 싼 기름 값을 저장해 주자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
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;
}
|
cs |
이러한 풀이가 왜 항상 최소 비용을 구할 수 있는지 생각해보자.
일반적인 다익스트라 문제에서는 최단 경로는 일차원 배열을 이용해 구하게 된다.
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)도 있으니 해결해보자.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
[백준] No.9376 - 탈옥 (C++, 다익스트라) (0) | 2021.05.09 |
---|---|
[백준] No.1854 - K번째 최단경로 찾기 (C++, 다익스트라) (0) | 2021.05.03 |
[백준] No.1162 - 도로포장 (C++, 다익스트라) (1) | 2021.04.30 |
[백준] No.1238 - 파티 (C++, 다익스트라) (0) | 2021.04.29 |
[백준] No.2536 - 버스 갈아타기 (C++, BFS) (0) | 2021.04.25 |