문제링크 : https://www.acmicpc.net/problem/1261
이 문제는 BFS 또는 다익스트라 알고리즘으로 해결할 수 있었습니다.
이 문제에서 저는 다익스트라 알고리즘을 채택했습니다.
기존의 문제들은 노드에서 간선의 가중치로 최단거리를 판별하였으나, 이렇게
grid한 맵에서 최단거리를 찾을 땐 가중치가 없는 경우가 많은것 같습니다.
게임을 예로들면, 진흙이나 강 등의 좌표로 갈 때는 가중치를 높게 주어서 최대한 우회를 하거나 가로지를땐 속도를 낮추면 되는데, 이 문제에 그러한 개념을 적용하자면 다음과 같이 하면 됩니다.
이 문제는, 벽을 뚫고가느냐 마느냐. 그것이 문제입니다.
따라서 벽을 뚫고가면, cost를 +1 해주고, 벽을 뚫고가지 않으면 cost + 0을 해주면 되는 문제 입니다.
문제에서 시점과 종점을 주고 있으므로, 최종 출력은 distance[x][y]를 하면 되는 문제 입니다.
소스코드 :
이 문제는 BFS 또는 다익스트라 알고리즘으로 해결할 수 있었습니다.
이 문제에서 저는 다익스트라 알고리즘을 채택했습니다.
기존의 문제들은 노드에서 간선의 가중치로 최단거리를 판별하였으나, 이렇게
grid한 맵에서 최단거리를 찾을 땐 가중치가 없는 경우가 많은것 같습니다.
게임을 예로들면, 진흙이나 강 등의 좌표로 갈 때는 가중치를 높게 주어서 최대한 우회를 하거나 가로지를땐 속도를 낮추면 되는데, 이 문제에 그러한 개념을 적용하자면 다음과 같이 하면 됩니다.
이 문제는, 벽을 뚫고가느냐 마느냐. 그것이 문제입니다.
따라서 벽을 뚫고가면, cost를 +1 해주고, 벽을 뚫고가지 않으면 cost + 0을 해주면 되는 문제 입니다.
문제에서 시점과 종점을 주고 있으므로, 최종 출력은 distance[x][y]를 하면 되는 문제 입니다.
소스코드 :
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#define INF 987654321
using namespace std;
int dirX[4]{ 1,0,-1,0 };
int dirY[4]{ 0,1,0,-1 };
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, m;
cin >> m >> n;
vector<vector<int> > graph(n + 2, vector<int>(m + 2));
// pq의 구성은 {가중치, {x좌표, y좌표}} 임.
priority_queue< pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater< pair<int, pair<int, int> > > > pq;
// 거리는 INF로 초기화 시켜놓음.
vector<vector<int> > distance(n + 2, vector<int>(m + 2, INF));
cin.clear();
cin.ignore();
for (int i = 1; i <= n; i++) {
string str;
getline(cin, str);
for (int j = 1; j <= m; j++) {
graph[i][j] = str[j-1] - 48;
}
}
// 초기값으로 pq에 가중치 0, 좌표 1.1 을 넣음.
pq.push({ 0,{1,1} });
distance[1][1] = 0;
while (!pq.empty()) {
int nodeX = pq.top().second.second;
int nodeY = pq.top().second.first;
int cost = pq.top().first;
pq.pop();
for (int i = 0; i < 4; i++) {
int tmpX = nodeX + dirX[i];
int tmpY = nodeY + dirY[i];
// 가려는 좌표가 범위를 넘는다면, 그 좌표는 제외시킴.
if (tmpX == 0 || tmpX > m || tmpY == 0 || tmpY > n)
continue;
// (1.1)에서 출발해서 (tmpX, tmpY)로 가는 거리 -이 문제에서는 벽을 몇번 뚫었냐- 가
// (nodeX, nodeY)에서 cost 더한것 보다 작은지 판단 후 최단거리 갱신.
// for(1:4)에서 여러 좌표가 중첩되므로, 결국엔 가장 벽을 뚫지 않는 거리만큼으로 갱신 됨.
if (distance[nodeY][nodeX] + cost < distance[tmpY][tmpX]) {
if (graph[tmpY][tmpX] == 1) {
pq.push({ cost + 1,{ tmpY,tmpX } });
distance[tmpY][tmpX] = cost + 1;
}
else {
pq.push({ cost,{ tmpY, tmpX } });
distance[tmpY][tmpX] = cost;
}
}
}
}
cout << distance[n][m] << endl;
}
| cs |
댓글
댓글 쓰기