[백준 1584] 게임 (C++)

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

문제

---

세준이는 위험한 지역에서 탈출하는 게임을 하고 있다. 이 게임에는 세준이가 들어갈 수 없는 죽음의 구역이 있고, 들어가서 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역이 있다. 그리고, 자유롭게 생명의 위협없이 움직일 수 있는 안전한 구역이 있다. (안전한 구역은 죽음의 구역과 위험한 구역을 제외한 나머지 이다.)

세준이는 (0, 0)에서 출발해서 (500, 500)으로 가야 한다. 세준이는 위, 아래, 오른쪽, 왼쪽으로만 이동할 수 있다. 현재 세준이는 (0, 0)에 있다. 그리고, 게임 판을 벗어날 수는 없다.

세준이가 (0, 0)에서 (500, 500)으로 갈 때 잃는 생명의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 반대 모서리이다. 그 다음 줄에는 죽음의 구역의 수 M이 주어진다. 다음 줄부터 M개의 줄에는 죽음의 구역의 정보가 위험한 구역의 정보와 같이 주어진다. 주어지는 구역은 모두 겹칠 수 있으며, 서로 다른 구역이 겹칠 때는, 더 심한 구역이 해당된다. 예를 들어, 죽음+위험 = 죽음, 위험+안전 = 위험, 위험+위험 = 위험, 죽음+안전 = 죽음이다. 위험한 구역이 아무리 겹쳐도 생명은 1씩 감소된다. 생명의 감소는 구역에 들어갈 때만, 영향을 미친다. 예를 들어, (500, 500)이 위험한 구역일 때는, (500, 500)에 들어갈 때, 생명이 1 감소되지만, (0, 0)이 위험한 구역이더라도 생명은 감소되지 않는다. 마찬가지로, (0, 0)이 죽음의 구역이더라도 세준이는 이미 그 곳에 있으므로 세준이에게 영향을 미치지 않는다. N과 M은 50보다 작거나 같은 자연수이다.

출력

---

첫째 줄에 정답을 출력한다. 만약 (500, 500)으로 갈 수 없을 때는 -1을 출력한다.

 

문제 풀이

---

다익스트라 문제.

 

상하좌우 이동이 가능한데 (탐색시) 이전에 방문한 곳도 더 적은 생명을 잃을 수 있다면 해당 구역을 다시 탐색할 수 있으므로 다익스트라를 사용한다.

 

생명이 많은 순, 위치 순으로 우선순위 큐에서 빠져나올 수 있도록 하고, 큐의 top에 해당하는 값을 꺼내며 상하좌우 4칸으로 이동 가능한지 확인한다. 해당 위치까지의 생명을 저장하는 2차원 배열의 값과, 현재 칸에서 다음 칸으로 이동하여 최종적으로 만들어지는 생명의 값과 비교하여 업데이트해주고 큐에 넣는다. 해당 방식으로 큐가 빌 때까지 탐색한다. [500][500]에 방문하지 못했다면 -1을 출력해주면 되고, 나머지는 잃은 생명의 값을 출력해주면 된다.

#include <iostream>
#include <queue>
#define INF 987654321
using namespace std;

int dx[] = { -1, 0, 0, 1 };
int dy[] = { 0, -1, 1, 0 };

struct info
{
	int x;
	int y;
	int life;
	info(int a, int b, int c)
	{
		x = a;
		y = b;
		life = c;
	}
};

struct cmp
{
	bool operator()(info& i1, info& i2)
	{
		if (i1.life > i2.life)
		{
			return false;
		}
		else if (i1.life == i2.life)
		{
			if (i1.x > i2.x)
			{
				return false;
			}
			else if (i1.x == i2.x)
			{
				return i1.y < i2.y;
			}
			else
			{
				return true;
			}
		}
		else
		{
			return true;
		}
	}
};

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int** map = new int*[501];
	int** life = new int*[501];
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 0; i < 501; i++)
	{
		map[i] = new int[501];
		life[i] = new int[501];
		for (int j = 0; j < 501; j++)
		{
			map[i][j] = 0;
			life[i][j] = INF;
		}
	}
	life[0][0] = 1000;
	int N, M;
	int x1, x2, y1, y2;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = min(x1, x2); i <= max(x1, x2); i++)
		{
			for (int j = min(y1, y2); j <= max(y1, y2); j++)
			{
				map[i][j] = -1;
			}
		}
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = min(x1, x2); i <= max(x1, x2); i++)
		{
			for (int j = min(y1, y2); j <= max(y1, y2); j++)
			{
				map[i][j] = -2;
			}
		}
	}
	pq.push(info(0, 0, 1000));
	while (!pq.empty())
	{
		info current = pq.top();
		pq.pop();
		for (int i = 0; i < 4; i++)
		{
			int nextX = current.x + dx[i];
			int nextY = current.y + dy[i];
			if (nextX >= 0 && nextX <= 500 && nextY >= 0 && nextY <= 500 && map[nextX][nextY] != -2)
			{
				if (map[nextX][nextY] == -1 && (current.life - 1 > life[nextX][nextY] || life[nextX][nextY]== INF))
				{
					life[nextX][nextY] = current.life - 1;
					pq.push(info(nextX, nextY, current.life - 1));
				}
				else if (map[nextX][nextY]==0 && (current.life > life[nextX][nextY] || life[nextX][nextY] == INF))
				{
					life[nextX][nextY] = current.life;
					pq.push(info(nextX, nextY, current.life));
				}
			}
		}
	}
	if (life[500][500] == INF)
	{
		cout << -1 << "\n";
	}
	else
	{
		cout << 1000 - life[500][500] << "\n";
	}
	return 0;
}