PS/BOJ
[알고리즘] 백준 1584번: 게임 (C++)
도비(Doby)
2021. 12. 7. 17:12
https://www.acmicpc.net/problem/1584
1584번: 게임
첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의
www.acmicpc.net
1) 위험한 구역은 1을 대입, 죽음의 구역은 2를 대입
2) 다익스트라를 돌려 2가 나오면 continue 시킴
3) x1, y1, x2, y2를 입력받으면 x1 > x2 혹은 y1 > y2일 때 둘을 swap 시키는 작업을 해주었음
4) 다익스트라를 돌리고 나서 (500, 500)이 INF라면 -1 출력 아니라면 최소 비용 출력
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#define MAX 500 + 1
#define INF 987654321
#define pii pair<int, int>
using namespace std;
int map[MAX][MAX];
typedef struct {
int y, x;
} Direction;
Direction dir[4] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
struct cmp {
bool operator()(pair<pii, int>& a, pair<pii, int>& b) {
return a.second > b.second;
}
};
vector<vector<int>> dist(MAX, vector<int>(MAX, INF));
void dijkstra(int row, int col) {
priority_queue<pair<pii, int>, vector<pair<pii, int>>, cmp> pq;
dist[row][col] = 0;
pq.push({ {row, col}, 0 });
while (!pq.empty()) {
int y = pq.top().first.first;
int x = pq.top().first.second;
int cost = pq.top().second;
pq.pop();
if (dist[y][x] < cost) continue;
for (int i = 0; i < 4; i++) {
int dy = y + dir[i].y;
int dx = x + dir[i].x;
if (dy < 0 || dy >= MAX || dx < 0 || dx >= MAX) continue;
if (map[dy][dx] == 2) continue;
int nextCost = map[dy][dx];
if (cost + nextCost < dist[dy][dx]) {
dist[dy][dx] = cost + nextCost;
pq.push({ {dy, dx}, dist[dy][dx] });
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n;
for (int i = 0, x1, y1, x2, y2; i < n; i++) {
cin >> x1 >> y1 >> x2 >> y2;
if (y1 > y2) {
int temp = y2;
y2 = y1;
y1 = temp;
}
if (x1 > x2) {
int temp = x2;
x2 = x1;
x1 = temp;
}
for (int j = y1; j <= y2; j++) {
for (int k = x1; k <= x2; k++) {
map[j][k] = 1;
}
}
}
cin >> m;
for (int i = 0, x1, y1, x2, y2; i < m; i++) {
cin >> x1 >> y1 >> x2 >> y2;
if (y1 > y2) {
int temp = y2;
y2 = y1;
y1 = temp;
}
if (x1 > x2) {
int temp = x2;
x2 = x1;
x1 = temp;
}
for (int j = y1; j <= y2; j++) {
for (int k = x1; k <= x2; k++) {
map[j][k] = 2;
}
}
}
dijkstra(0, 0);
if (dist[500][500] == INF) cout << -1;
else cout << dist[500][500];
return 0;
}