백준 16973 - 직사각형 탈출

문제 설명

크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.

격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.

직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 왼쪽 위가 (Sr, Sc)에 위치하는 크기가 H x W인 직사각형의 왼쪽 위를 (Fr, Fc)까지 최단 길이로 이동시켜야 한다.

 

전형적인 최단 경로 찾기 문제이다.

추가적인 조건은 이동하는 직사각형의 크기를 고려해야 한다는 점이다.

 

기본적인 BFS로 진행하며 직사각형의 크기 안에 1이 존재한다면 이동을 제한시키는 방법을 사용하면 정답을 구할 수 있다.

이때 2중 for문으로 직사각형 크기안에 장애물 여부를 판단하면 시간 초과가 발생한다.

이를 개선하기 위해서는 누적합을 사용하면 된다.

2차원 누적합을 통해 특정 구간안에 1의 개수를 $O(1)$만에 구할 수 있기 때문이다.

for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= M; j++)
    {
        sum[i][j] = sum[i][j - 1] + board[i][j];
    }
}

for (int j = 1; j <= M; j++)
{
    for (int i = 1; i <= N; i++)
    {
        sum[i][j] += sum[i - 1][j];
    }
}

 

bool Check(int y, int x)
{
	int rightY = y + H - 1;
	int rightX = x + W - 1;
	
	if (rightY > N || rightX > M) return false;
	
	return sum[rightY][rightX] - sum[y - 1][rightX] - sum[rightY][x - 1] + sum[y - 1][x - 1] == 0;
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, M, H, W, Sr, Sc, Fr, Fc;
vector<vector<int>> board;
vector<vector<int>> sum;
vector<vector<bool>> visited;

int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };

bool Check(int y, int x)
{
	int rightY = y + H - 1;
	int rightX = x + W - 1;

	if (rightY > N || rightX > M) return false;

	return sum[rightY][rightX] - sum[y - 1][rightX] - sum[rightY][x - 1] + sum[y - 1][x - 1] == 0;
}

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> N >> M;
	board.resize(N + 1, vector<int>(M + 1));
	sum.resize(N + 1, vector<int>(M + 1));
	visited.resize(N + 1, vector<bool>(M + 1, false));
	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> board[i][j];
		}
	}

	cin >> H >> W >> Sr >> Sc >> Fr >> Fc;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			sum[i][j] = sum[i][j - 1] + board[i][j];
		}
	}

	for (int j = 1; j <= M; j++)
	{
		for (int i = 1; i <= N; i++)
		{
			sum[i][j] += sum[i - 1][j];
		}
	}

	
	visited[Sr][Sc] = true;
	queue<pair<int, int>> q;
	q.push({ Sr, Sc });
	int depth = 1;
	bool bEnd = false;

	while (!q.empty())
	{
		auto size = q.size();
		for (int k = 0; k < size; k++)
		{
			auto [y, x] = q.front();
			q.pop();

			for (int i = 0; i < 4; i++)
			{
				int newY = y + dy[i];
				int newX = x + dx[i];

				if (newY <= 0 || newY > N || newX <= 0 || newX > M) continue;
				if (visited[newY][newX]) continue;
				if (!Check(newY, newX)) continue;

				if (newY == Fr && newX == Fc)
				{
					bEnd = true;
					break;
				}

				visited[newY][newX] = true;
				q.push({ newY, newX });
			}

			if (bEnd) break;
		}

		if (bEnd) break;
		depth++;
	}

	if (bEnd) cout << depth;
	else cout << -1;

	return 0;
}

---