문제링크 : https://www.acmicpc.net/problem/4485
이 문제는, 가중치가 있는 grid 형태의 맵에서
해당 좌표만큼의 최단거리를 찾는 문제 입니다.
기존엔 시점의 가중치를 0으로 두고 시작하였지만, 이 문제는 던전을 들어갔을 때 무조건 가중치만큼 돈을 잃는 것이므로, 시점에서조차 cost를 주어야 했습니다.
다익스트라 방법을 사용할 때는 다음의 사항을 숙지하고 있어야 합니다.
1. PQ에서 값을 꺼낼 때, 현재 모든 distance는 최소이다.
2. 현재 distance에서 어떤 위치(혹은 간선)으로 이동했을 때,
(현재 distance + 어떤위치의 가중치) < 어떤위치의 distance 이면 갱신한다.
소스코드 :
이 문제는, 가중치가 있는 grid 형태의 맵에서
해당 좌표만큼의 최단거리를 찾는 문제 입니다.
기존엔 시점의 가중치를 0으로 두고 시작하였지만, 이 문제는 던전을 들어갔을 때 무조건 가중치만큼 돈을 잃는 것이므로, 시점에서조차 cost를 주어야 했습니다.
다익스트라 방법을 사용할 때는 다음의 사항을 숙지하고 있어야 합니다.
1. PQ에서 값을 꺼낼 때, 현재 모든 distance는 최소이다.
2. 현재 distance에서 어떤 위치(혹은 간선)으로 이동했을 때,
(현재 distance + 어떤위치의 가중치) < 어떤위치의 distance 이면 갱신한다.
소스코드 :
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#define INF 987654321
using namespace std;
int dirX[4] { 0,0,-1,1 };
int dirY[4]{ 1,-1,0,0 };
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int problemNumber = 1;
int n;
while ((cin >> n) && n != 0) {
vector<vector<int> > graph(n + 2, vector<int>(n + 2));
vector<vector<int> > distance(n + 2, vector<int>(n + 2, INF));
// cost, x, y 순임
priority_queue< pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >,
greater< pair<int, pair<int, int> > > > pq;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> graph[i][j];
}
}
//1.1에서 start
pq.push({ graph[1][1], {1,1} });
distance[1][1] = graph[1][1];
while (!pq.empty()) {
int cost = pq.top().first;
int x = pq.top().second.first;
int y = pq.top().second.second;
pq.pop();
for (int i = 0; i < 4; i++) {
int dx = x + dirX[i];
int dy = y + dirY[i];
if (dx == 0 || dx > n || dy == 0 || dy > n)
continue;
if (distance[dx][dy] > cost + graph[dx][dy]) {
distance[dx][dy] = cost + graph[dx][dy];
pq.push({ distance[dx][dy], {dx,dy} });
}
}
}
cout << "Problem "<<problemNumber++<<": "<< distance[n][n] << endl;
}
}
| cs |
댓글
댓글 쓰기