[BOJ/Gold 5] 백준 2194 유닛 이동시키기(C++)

문제 링크

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

2194번: 유닛 이동시키기

문제

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

유닛은 상하좌우의 네 방향으로만 움직일 수 있다. 단, 유닛의 일부분이 장애물이 설치된 부분(위의 예에서 색이 칠해진 부분)을 지날 경우, 위의 예에서는 시작 위치에서 위로 이동하는 경우는 허용되지 않는다. 위의 예는 유닛을 오른쪽으로 세 칸, 위쪽으로 세 칸 움직이면 목적지에 도달할 수 있고, 이 경우가 가장 적은 이동 회수를 거치는 경우이다. 이동하는 도중에 유닛이 맵 밖으로 나가는 경우는 허용되지 않는다.

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

입력

첫째 줄에 다섯 개의 정수 N, M(1 ≤ N, M ≤ 500), A, B(1 ≤ A, B ≤ 10), K(0 ≤ K ≤ 100,000)가 주어진다. 다음 K개의 줄에는 장애물이 설치된 위치(행 번호, 열 번호)가 주어진다. 그 다음 줄에는 시작점의 위치와 도착점의 위치가 주어진다. 시작점의 위치와 도착점의 위치는 제일 왼쪽 제일 위의 한 점만 주어진다. 시작점의 위치와 도착점의 위치는 같지 않다.

출력

첫째 줄에 답을 출력한다. 이동이 불가능한 경우에는 -1을 출력한다.

예제 입력 1

5 5 2 2 3
2 2
3 2
3 3
4 1
1 4

예제 출력 1

6

알고리즘 분류

• 그래프 탐색

풀이

움직이는 유닛의 크기가 1X1칸이 아니라 AXB칸인 것 말고는 일반적인 BFS 문제와 동일하다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 505
#define LL long long
#define INF 2e9

using namespace std;
int N, M, A, B, K;
pair<int, int> Start_Pos, End_Pos;
int MAP[MAX][MAX];
bool visited[MAX][MAX];
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };
int answer = 0;

bool isThereBlock(int Y, int X) {
	for (int i = Y; i < (Y + A); i++) {
		for (int j = X; j < (X + B); j++) {
			if (MAP[i][j] == -1) {
				return false;
			}
		}
	}
	return true;
}

int BFS(int Y, int X) {
	queue<pair<pair<int, int>, int> > Q;
	visited[Y][X] = true;
	Q.push(make_pair(make_pair(Y, X), 0));

	while (!Q.empty()) {
		int CurY = Q.front().first.first;
		int CurX = Q.front().first.second;
		int CurCost = Q.front().second;
		Q.pop();

		if ((CurY == End_Pos.first) && (CurX == End_Pos.second)) {
			return CurCost;
		}

		for (int i = 0; i < 4; i++) {
			int nextY = CurY + moveY[i];
			int nextX = CurX + moveX[i];
			if ((nextY >= 1) && (nextY + A - 1 <= N) && (nextX >= 1) && (nextX + B - 1 <= M) && (!visited[nextY][nextX]) && isThereBlock(nextY, nextX)) {
				visited[nextY][nextX] = true;
				Q.push(make_pair(make_pair(nextY, nextX), CurCost + 1));
			}
		}
	};

	return -1;
}

int main() {
	FIRST
	cin >> N >> M >> A >> B >> K;
	for (int i = 0; i < K; i++) {
		int Y, X;
		cin >> Y >> X;
		MAP[Y][X] = -1;
	}
	cin >> Start_Pos.first >> Start_Pos.second;
	cin >> End_Pos.first >> End_Pos.second;
	cout << BFS(Start_Pos.first, Start_Pos.second) << "\n";

	return 0;
}