[백준/BOJ] 백준 2194번 : 유닛 이동시키기

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

2194번: 유닛 이동시키기

유닛이 움직일 수 있는 위치를 고려해서 bfs를 통해 목적지로 이동하는데 필요한 최소 이동 횟수를 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

int n, m, a, b, k;
int board[501][501];
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int discoverd[501][501];
int depth[501][501];

//유닛을 there 방향으로 움직이면 장애물이랑 안겹치는지 확인
bool Check(pair<int,int> there)
{

	for(int i=there.first; i < there.first+a; i++)
		for (int j = there.second; j < there.second+b; j++)
		{
			//장애물이랑 겹칠때
			if (board[i][j] == 1)
				return false;
		}

	return true;
}

//start위치의 유닛을 dest위치로 이동하는데 필요한 최소 이동횟수를 bfs를 통해 구한다
int Solve(pair<int, int> start, pair<int, int> dest)
{
	discoverd[start.first][start.second] = 1;
	depth[start.first][start.second] = 0;

	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//목적지에 도착했을때
		if (here.first == dest.first && here.second == dest.second)
			return depth[here.first][here.second];

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
			
			if (there.first >= 1 && there.first + a-1 <= n && there.second >= 1 && there.second + b-1 <= m && Check(there) && discoverd[there.first][there.second] == 0)
			{
				discoverd[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;

				q.push(there);
			}
		}
	}

	return -1;
}

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

	memset(board, 0, sizeof(board));
	memset(discoverd, 0, sizeof(discoverd));

	int x, y;
	pair<int, int> start;
	pair<int, int> dest;

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

	for (int i = 0; i < k; i++)
	{
		cin >> x >> y;
		board[x][y] = 1;
	}

	cin >> x >> y;
	start = make_pair(x, y);

	cin >> x >> y;
	dest = make_pair(x, y);

	cout << Solve(start, dest);

	return 0;
}