[알고리즘] 백준 1584번: 게임 (C++)

https://www.acmicpc.net/problem/1584

1584번: 게임

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;
}