[BOJ/Gold 4] 백준 16973 직사각형 탈출(C++)

문제 링크

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

16973번: 직사각형 탈출

문제

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

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

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

 

입력

첫째 줄에 격자판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 각 칸의 정보가 주어진다. 0은 빈 칸, 1은 벽이다.

마지막 줄에는 직사각형의 크기 H, W, 시작 좌표 Sr, Sc, 도착 좌표 Fr, Fc가 주어진다.

격자판의 좌표는 (r, c) 형태이고, r은 행, c는 열이다. 1 ≤ r ≤ N, 1 ≤ c ≤ M을 만족한다.

출력

첫째 줄에 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 1 ≤ H ≤ N
• 1 ≤ W ≤ M
• 1 ≤ Sr ≤ N-H+1
• 1 ≤ Sc ≤ M-W+1
• 1 ≤ Fr ≤ N-H+1
• 1 ≤ Fc ≤ M-W+1
• 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.

예제 입력 1

4 5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
2 2 1 1 1 4

예제 출력 1

7

아래, 아래, 오른쪽, 오른쪽, 오른쪽, 위, 위

예제 입력 2

6 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
2 3 1 1 5 5

예제 출력 2

8

알고리즘 분류

• 그래프 탐색

풀이

백준 2194 - 유닛 이동시키기와 비슷한 문제라고 생각하여 같은 로직으로 짜 봤으나 시간 초과에 걸렸다.

직사각형이 이동할 때, 좌표가 변하는 지점들에만 벽이 있는지 확인해주는 식으로 시간을 줄여주었다.

코드

#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 1005
#define LL long long
#define INF 2e9

using namespace std;
int N, M, H, W, SR, SC, FR, FC;
int MAP[MAX][MAX];
bool visited[MAX][MAX];
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };

bool isThereWall(int Y, int X, int Dir) {
	if (Dir == 0) {
		for (int i = X; i < (X + W); i++) {
			if (MAP[Y][i] == 1) {
				return false;
			}
		}
	}
	else if (Dir == 1) {
		for (int i = Y; i < (Y + H); i++) {
			if (MAP[i][X] == 1) {
				return false;
			}
		}
	}
	else if (Dir == 2) {
		int nextY = Y + H - 1;
		if (nextY > N) {
			return false;
		}
		for (int i = X; i < (X + W); i++) {
			if (MAP[nextY][i] == 1) {
				return false;
			}
		}
	}
	else if (Dir == 3) {
		int nextX = X + W - 1;
		if (nextX > M) {
			return false;
		}
		for (int i = Y; i < (Y + H); i++) {
			if (MAP[i][nextX] == 1) {
				return false;
			}
		}
	}
	return true;
}

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

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

		if ((CurR == FR) && (CurC == FC)) {
			return CurCost;
		}

		for (int i = 0; i < 4; i++) {
			int nextR = CurR + moveY[i];
			int nextC = CurC + moveX[i];
			if ((nextR >= 1) && (nextR <= N) && (nextC >= 1) && (nextC <= M) && (!visited[nextR][nextC]) && (MAP[nextR][nextC] == 0)) {
				visited[nextR][nextC] = true;
				if (isThereWall(nextR, nextC, i)) {
					Q.push(make_pair(make_pair(nextR, nextC), CurCost + 1));
				}
			}
		}
	};

	return -1;
}

int main() {
	FIRST
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> MAP[i][j];
		}
	}
	cin >> H >> W >> SR >> SC >> FR >> FC;
	cout << BFS() << "\n";

	return 0;
}