BOJ 2194번 유닛 이동시키기 C++

BOJ : https://www.acmicpc.net/problem/2194

2194번: 유닛 이동시키기

 

스타크래프트와 같은 게임을 하다 보면 어떤 유닛을 목적지까지 이동시켜야 하는 경우가 종종 발생한다. 편의상 맵을 N×M 크기의 2차원 행렬로 생각하자. 또한 각각의 유닛은 크기를 가질 수 있는데, 이를 A×B 크기의 2차원 행렬로 생각하자. 아래는 5×5 크기의 맵과 2×2 크기의 유닛에 대한 한 예이다. S는 시작점을 나타내며 E는 끝점을 나타낸다.

유닛은 상하좌우의 네 방향으로만 움직일 수 있다. 단, 유닛의 일부분이 장애물이 설치된 부분(위의 예에서 색이 칠해진 부분)을 지날 경우, 위의 예에서는 시작 위치에서 위로 이동하는 경우는 허용되지 않는다.

위의 예는 유닛을 오른쪽으로 세 칸, 위쪽으로 세 칸 움직이면 목적지에 도달할 수 있고, 이 경우가 가장 적은 이동 회수를 거치는 경우이다. 이동하는 도중에 유닛이 맵 밖으로 나가는 경우는 허용되지 않는다.

맵의 정보와 유닛의 정보가 주어졌을 때, 유닛을 목적지까지 움직이기 위해 필요한 최소의 이동 회수를 구하는 프로그램을 작성하시오.

 

백준 2194번 유닛 이동시키기 문제입니다.

구현부류에 해당하고 간단한 BFS 문제였습니다.

 

시작지점의 유닛 좌측상단의 좌표를 기준으로 하기 때문에

BFS 탐색간에 유닛의 크기만큼 전체가 장애물을 피해서 이동이 가능한지 판단해주시면서 탐색해주시면 됩니다.

 

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

queue<pair<pii, int> > q;

int n, m, a, b, k, dx, dy;
bool visit[502][502];
bool arr[502][502];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,1,-1 };

bool test(int y, int x) {

	for (int i = 0; i < a; i++)
		for (int j = 0; j < b; j++)
			if (arr[y + i][x + j]) return false;

	return true;
}


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m >> a >> b >> k;

	for (int i = 0; i < k; i++) {
		cin >> dy >> dx;
		arr[dy][dx] = true;
	}

	int sy, sx, ey, ex;
	cin >> sy >> sx >> ey >> ex;
	q.push({ {sy,sx},0 });
	int answer = -1;

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (y == ey && x == ex) {
			answer = cnt;
			break;
		}

		for (int i = 0; i < 4; i++) {
			int yy = y + my[i];
			int xx = x + mx[i];
			if (yy > 0 && yy + a - 1 <= n && xx > 0&& xx + b - 1 <= m && !visit[yy][xx] && test(yy, xx)) {
				visit[yy][xx] = true;
				q.push({ {yy,xx},cnt + 1 });
			}
		}
	}

	cout << answer;

	return 0;
}