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

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

16973번: 직사각형 탈출

 

BFS 문제다.

배열의 한 칸을 기준으로 움직이는 것이 아닌 직사각형 묶음으로 움직이는 것이다.

움직이는 방향의 변의 길이만큼 확인을 해야 한다.

예를 들어 우측 방향으로 이동을 해야 한다면 별로 표시된 부분이 벽인지 혹은 범위를 벗어나는지 검사해야 한다.

	직	사	*
	각	형	*

 

처음에는 dx, dy 배열을 사용하지 않고 상하좌우를 각각 나눠 검사하고 큐에 넣었다.

검사하는 방법은 우측을 예시로 들면 현재 값 기준에서 열에 직사각형 너비만큼 더해 고정하고 행을 변환시켰다.

수치로 보면 위의 경우 현재 값은 (2, 2)고, 열은 2 + 2 = 4로 고정, 행을 반복문으로 2, 3 검사했다.

반복문에서 조건을 다 통과하면 변수 값을 변환시켜 큐에 넣었다.

// 하
		for (int i = 0; i < w; i++) {
			int xx = curx + h;
			int yy = cury + i;
			
			range = 1;
			if (xx > n) break;
			if (board[xx][yy]) break;
			if (board[curx + 1][cury]) break;
			range = 0;
			}

		if (range == 0) {
			board[curx + 1][cury] = board[curx][cury] + 1;
			q.push({ curx + 1, cury });

			if (curx + 1 == fx && cury == fy) return board[curx][cury];
		}

위와 같은 코드가 상 하 좌 우에 맞게 4개가 존재했다.

정말 화가 나게도 문제를 못 찾겠고 어떤 예제를 넣어봐도 다 맞는데 2% 밖에 가지 못했다...

끝까지 반례를 찾아보려 했으나 못 찾았고...

 

다른 방법으로 보편적인 BFS 처럼 dx, dy 배열을 사용했고 움직인 좌표에서 직사각형 전체를 검사했다.

그렇게 코드를 짜보니 처참하게 시간 초과...^^

 

그래서 찾은 방법은 위 두 방법을 합치는 것이다.

dx, dy 배열을 이용하여 좌표를 이동하고 상하좌우에 맞게 검사를 해주는 것이다.

이렇게 하니 전체 직사각형을 검사하기 위해 2중 반복문을 사용했던 것이 단일 반복문이 됐다.

 

#include <iostream>
#include <queue>
using namespace std;

int n, m, h, w, sx, sy, fx, fy;
int board[1001][1001];
// 상하좌우 탐색을 위함
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

bool check(int x, int y, int i) {
	// 상
	if (i == 0) {
		for (int i = y; i < y + w; i++)
			if (board[x][i] == -1) return 0;
	}
	
	// 우
	else if (i == 1) {
		if (y + w - 1 > m) return 0;
		for (int i = x; i < x + h; i++)
			if (board[i][y + w - 1] == -1) return 0;
	}

	// 하
	else if (i == 2) {
		if (x + h - 1 > n) return 0;
		for (int i = y; i < y + w; i++)
			if (board[x + h - 1][i] == -1) return 0;
	}

	// 좌
	else {
		for (int i = x; i < x + h; i++)
			if (board[i][y] == -1) return 0;
	}

	return 1;
}

int BFS(int x, int y) {
	// <x, y>
	queue<pair<int, int>> q;

	board[x][y] = 1;
	q.push({ x, y });
	
	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		int curx = q.front().first;
		int cury = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int xx = curx + dx[i];
			int yy = cury + dy[i];

			// 도착지에는 확실히 직사각형이 들어갈 수 있으므로 검사 전 반환
			if (xx == fx && yy == fy) return board[curx][cury];

			// 범위를 벗어나거나 방문한 적 있으면 continue
			if (xx < 1 || yy < 1 || xx > n || yy > m) continue;
			if (board[xx][yy]) continue;

			// 직사각형이 차지하는 너비에 벽이 없는지 확인
			if (check(xx, yy, i)) {
				q.push({ xx, yy });
				board[xx][yy] = board[curx][cury] + 1;
			}
		}
	}
	return -1;
}

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> board[i][j];
			if (board[i][j]) board[i][j] = -1;
		}

	cin >> h >> w >> sx >> sy >> fx >> fy;

	cout << BFS(sx, sy);
}

 

시간초과 났던 서러움이다...😥

 

참고로 main에 처음 두 줄은 입출력 속도를 빠르게 해 준다.

속도가 반으로 줄어드는 것을 볼 수 있다.

 

험난 했던 직사각형 탈출 끗😎