[BOJ/Gold 5] 백준 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을 출력한다.

 

예제 입력 1

1
500 0 0 500
1
0 0 0 0

예제 출력 1

1000

예제 입력 2

0
0

예제 출력 2

0

예제 입력 3

2
0 0 250 250
250 250 500 500
2
0 251 249 500
251 0 500 249

예제 출력 3

1000

예제 입력 4

2
0 0 250 250
250 250 500 500
2
0 250 250 500
250 0 500 250

예제 출력 4

-1

 

알고리즘 분류

• 그래프 탐색

 

풀이

주어진 범위를 가지고 위험한 구역과 죽음의 구역을 만든다.

죽음의 구역으로는 들어갈 수 없고, 위험한 구역으로 들어가면 생명력을 1 잃는다. 안전한 구역으로 들어가면 생명력을 잃지 않는다.

탐색하면서 변화하는 값이 0과 1뿐이므로, 0-1 BFS를 사용할 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
#define MAX 501
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, X1, Y1, X2, Y2;
int MAP[MAX][MAX];
int Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int Answer;

void init() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			Visited[i][j] = INF;
		}
	}
}

void setRange(int StartY, int EndY, int StartX, int EndX, int Value) {
	for (int i = StartY; i <= EndY; i++) {
		for (int j = StartX; j <= EndX; j++) {
			MAP[i][j] = Value;
		}
	}
}

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> X1 >> Y1 >> X2 >> Y2;
		if ((X1 <= X2) && (Y1 <= Y2)) {
			setRange(Y1, Y2, X1, X2, -1);
		}
		else if ((X1 >= X2) && (Y1 <= Y2)) {
			setRange(Y1, Y2, X2, X1, -1);
		}
		else if ((X1 <= X2) && (Y1 >= Y2)) {
			setRange(Y2, Y1, X1, X2, -1);
		}
		else if ((X1 >= X2) && (Y1 >= Y2)) {
			setRange(Y2, Y1, X2, X1, -1);
		}
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> X1 >> Y1 >> X2 >> Y2;
		if ((X1 <= X2) && (Y1 <= Y2)) {
			setRange(Y1, Y2, X1, X2, -2);
		}
		else if ((X1 >= X2) && (Y1 <= Y2)) {
			setRange(Y1, Y2, X2, X1, -2);
		}
		else if ((X1 <= X2) && (Y1 >= Y2)) {
			setRange(Y2, Y1, X1, X2, -2);
		}
		else if ((X1 >= X2) && (Y1 >= Y2)) {
			setRange(Y2, Y1, X2, X1, -2);
		}
	}
}

int bfs() {
	deque<pair<pair<int, int>, int> > DQ;
	Visited[0][0] = 0;
	DQ.push_front(make_pair(make_pair(0, 0), 0));

	while (!DQ.empty()) {
		int NowY = DQ.front().first.first;
		int NowX = DQ.front().first.second;
		int NowH = DQ.front().second;
		DQ.pop_front();

		if ((NowY == MAX - 1) && (NowX == MAX - 1)) {
			return NowH;
		}

		for (int i = 0; i < 4; i++) {
			int NextY = NowY + MoveY[i];
			int NextX = NowX + MoveX[i];
			if ((NextY >= 0) && (NextY < MAX) && (NextX >= 0) && (NextX < MAX)) {
				if ((MAP[NextY][NextX] == 0) && (Visited[NextY][NextX] > NowH)) {
					DQ.push_front(make_pair(make_pair(NextY, NextX), NowH));
					Visited[NextY][NextX] = NowH;
				}
				else if ((MAP[NextY][NextX] == -1) && (Visited[NextY][NextX] > NowH + 1)) {
					DQ.push_back(make_pair(make_pair(NextY, NextX), NowH + 1));
					Visited[NextY][NextX] = NowH + 1;
				}
			}
		}
	};

	return -1;
}

void settings() {
	Answer = bfs();
}

void printAnswer() {
	cout << Answer << "\n";
}

int main() {
    FASTIO

	init();
	input();
	settings();
	printAnswer();

    return 0;
}