[백준] 1584번 게임

1. 문제

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

이 게임에는 세준이가 들어갈 수 없는 죽음의 구역이 있고, 들어가서 한 번 움직일 때 마다 생명이 1씩 소모되는 위험한 구역이 있다. 그리고, 자유롭게 생명의 위협없이 움직일 수 있는 안전한 구역이 있다.
세준이가 (0, 0)에서 (500, 500)으로 갈 때 잃는 생명의 최솟값을 구하는 프로그램을 작성하시오.

입력으로는 처음에는 위험구역의 수 N과 구역의 좌표, 두번째로 죽음의 구역의 수 M과 구역의 좌표가 주어진다.
두 구역이 겹쳐지면 더 심한 구역의 효과가 적용된다.

출력으로 잃는 생명의 최솟값을 출력하고 (500, 500)으로 갈 수 없을때는 -1을 출력한다.

2. 풀이

이 문제는 넓이우선 탐색(BFS)의 변형인 0-1 BFS 문제이다. 간선의 가중치가 0 혹은 1인 그래프 위에서 움직이기 때문에 그렇게 이름이 붙여졌다.

일반적인 BFS 문제와 다른 점은 간선의 가중치가 있기 때문에
(1) 가중치가 더해지지 않은 좌표는 앞에,
(2) 가중치가 더해진 좌표는 뒤에 넣어 탐색을 한다.

이렇게 하면 가중치가 적은 순으로 꺼내 탐색을 하므로 잃는 생명의 최솟값을 구할 수 있다.

이를 위해 Deque이라는 자료구조를 사용하였다.

3. 코드

#include <iostream>
#include <queue>

using namespace std;

int map[505][501];
bool visit[501][501];

int routeX[] = {-1, 1, 0, 0}, routeY[] = {0, 0, -1, 1};

struct pos
{
	int x, y, dmg;
};

int main()
{
	int n, m;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int x1, x2, y1, y2;
		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)
	{
		int x1, x2, y1, y2;
		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)
				visit[i][j] = true;
	}

	bool check = true;
	deque<pos> dq;
	dq.push_front({0, 0, 0});
	while (!dq.empty())
	{
		auto p = dq.front();
		dq.pop_front();

		if (p.x == 500 && p.y == 500)
		{
			cout << p.dmg;
			check = false;
			break;
		}

		for (int i = 0; i < 4; ++i)
		{
			int tmpX = p.x + routeX[i];
			int tmpY = p.y + routeY[i];

			if (0 > tmpX || tmpX > 500 || 0 > tmpY || tmpY > 500 || visit[tmpX][tmpY])
				continue;

			else
			{
				visit[tmpX][tmpY] = true;


				if (map[tmpX][tmpY] == 1)
				{
					dq.push_back({tmpX, tmpY, p.dmg + 1});
				}
				else
				{
					dq.push_front({tmpX, tmpY, p.dmg});
				}
			}
		}
	}

	if (check)
		cout << "-1";
}

4. 후기

BFS의 변형 문제 중 하나이다.

그냥 BFS를 돌리게 되면 먼저 (500, 500)에 도달하게된 좌표가 생명력의 최소라는 보장이 없어 큐를 비울때까지 모두 탐색을 해야되고 이렇게 되면 바로 시간초과가 뜬다.

하지만 Deque을 사용하여 가중치별로 앞, 뒤로 넣어가며 탐색을 하면 가중치 순으로 나오게 되므로 먼저 나오는 좌표가 가장 적은 가중치라는 보장이 있게되어 풀 수 있게 된다.