[C++] 백준/BOJ - 16973 : 직사각형 탈출

---

문제 이해 단계

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

NxM 크기의 격자판이 주어지고, 크기가 HxW인 직사각형이 주어진다.
이동할 수 있는 칸은 0, 이동할 수 있는 칸은 1로 되어 있다.

직사각형의 가장 왼쪽 위의 칸이 처음에 주어지고,
도착 좌표가 주어진다.

이때 이 직사각형의 왼쪽 위가
도착좌표까지 갈 때 최단거리를 구하는 것

 

---

문제 접근 단계

직사각형의 크기가 있다는 점만 제외하고는

벽과 격자판이 존재한다는 점과
특정 지점까지 이동하는 최단 거리를 구해야 한다는 점에서
대표적인 BFS 문제라는 점이라는 것을 알 수 있다.

중요한 것은 직사각형이기 때문에
체크해야 할 부분이 하나가 아니라 여러 개로 늘어났다.

직사각형 왼쪽 위 칸이 도착 지점으로 가야 하므로,
이 문제에서는 왼쪽 위를 중심으로 보고 생각한다.

핵심은 이동 방향에 따라 어떻게,
그리고 얼마나 벽을 체크하는지가 중요하다.
이는 그림으로 표현하는 것이 간단하다.

그림으로 표현하면 이렇게 된다.
만약 3X2 직사각형이 존재한다고 했을 때

그림 표현

 

빨간 네모 - 중심이 되는 직사각형의 왼쪽 위 부분
노란 네모 - 일반적인 1x1 BFS에서의 이동 위치
점선 네모 - 이동했을 때 체크해야 할 영역

이렇게 확인할 수 있다.

BFS를 구성할 때, 이 점을 유의하면서 점선 부분을 체크한다.
점선 부분 중 하나라도 벽에 부딪히면 그쪽으로는 이동할 수 없다.

이는 코드를 통해 자세히 알아보겠다.

 

---

문제 구현 단계

bool InnerBfs(int s1, int s2, int i) {
	int x, y;
	switch (i) {
	case(0):
		x = s1;
		y = s2;
		for (int j = 0; j < H; j++) {
			if (map[x + j][y] == 1) return false;
		}
		break;
	case(1):
		x = s1;
		y = s2 + W - 1;
		if (y > M) return false;
		for (int j = 0; j < H; j++) {
			if (map[x + j][y] == 1) return false;
		}
		break;
	case(2):
		x = s1;
		y = s2;
		for (int j = 0; j < W; j++) {
			if (map[x][y+j] == 1) return false;
		}
		break;
	case(3):
		x = s1 + H - 1;
		y = s2;
		if (x > N) return false;
		for (int j = 0; j < W; j++) {
			if (map[x][y+j] == 1) return false;
		}
		break;
	}
	return true;

문제 접근 부분 그림처럼 점선 부분이 벽에 닿는지 체크하는 부분이다.
닿으면 false, 닿지 않으면 true를 반환한다.

매개변수 i는 이동 인덱스를 뜻한다.

i는 상하좌우를 뜻하는데 케이스에 따라
모두 다르게 체크해야 하므로 Switch문을 사용하였다.

왼쪽으로 이동(i == 0) 일 때는
왼쪽부터 세로로 H개를 더 체크해야 하므로
H-1만큼 1씩 더하면서 벽에 닿는지 체크한다.

오른쪽으로 이동(i == 1) 일 때는
오른쪽으로 세로로 H개이므로,
y를 (매개변수 y + 가로 - 1)로 직사각형 오른쪽 위로 옮긴다.

이후에는 왼쪽 위일 때와 같다.

위로 갈 때와 아래로 갈 때도 H에서 W로 바뀔 뿐
왼쪽과 오른쪽으로 이동하는 것과 동일하다.

이런 식으로 충돌을 체크하여 모두 통과하면 true를 반환한다.

int Bfs(int s1, int s2, int e1,int e2) {
	queue<pair<int, int>> q;
	q.push(make_pair(s1, s2));
	c[s1][s2] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		if (x == e1 && y == e2) return c[x][y] - 1;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || ny < 1 || nx > N || ny > M || map[nx][ny] == 1) continue;
			if (!c[nx][ny] && InnerBfs(nx, ny, i)) {
				c[nx][ny] = c[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
	return -1;
}

최단거리를 구하는 BFS 함수이다.
매개변수로 시작 좌표 s1, s2와 도착 좌표 e1, e2를 받는다.

방문을 뜻하는 c를 이동 횟수로 사용하여 답을 구한다.

일반적인 BFS와 다른 점은
방문하지 않은 노드임과 동시에 InnerBfs를 만족해야 한다는 점이다.

이를 모두 만족하면 현재 이동 횟수의 +1을 하여 다음 노드에 저장한다.
이후 queue에 넣고 x와 y값이 e1과 e2일 때까지 반복한다.

반환값은 그때의 c [x][y]-1의 값이다.

만약 큐가 다 빌 때까지 x와 y가 e1, e2가 아니라면
도달하지 못한 것이므로 -1을 반환한다.

main 함수 부분은 그냥 입력을 넣는 부분이기 때문에
전체 코드를 올리고 끝내겠다.

#include <iostream>
#include <queue>

using namespace std;

int N, M, H, W;
int map[1001][1001];
int c[1001][1001];

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

bool InnerBfs(int s1, int s2, int i) {
	int x, y;
	switch (i) {
	case(0):
		x = s1;
		y = s2;
		for (int j = 0; j < H; j++) {
			if (map[x + j][y] == 1) return false;
		}
		break;
	case(1):
		x = s1;
		y = s2 + W - 1;
		if (y > M) return false;
		for (int j = 0; j < H; j++) {
			if (map[x + j][y] == 1) return false;
		}
		break;
	case(2):
		x = s1;
		y = s2;
		for (int j = 0; j < W; j++) {
			if (map[x][y+j] == 1) return false;
		}
		break;
	case(3):
		x = s1 + H - 1;
		y = s2;
		if (x > N) return false;
		for (int j = 0; j < W; j++) {
			if (map[x][y+j] == 1) return false;
		}
		break;
	}
	return true;
}
int Bfs(int s1, int s2, int e1,int e2) {
	queue<pair<int, int>> q;
	q.push(make_pair(s1, s2));
	c[s1][s2] = 1;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		if (x == e1 && y == e2) return c[x][y] - 1;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || ny < 1 || nx > N || ny > M || map[nx][ny] == 1) continue;
			if (!c[nx][ny] && InnerBfs(nx, ny, i)) {
				c[nx][ny] = c[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
	return -1;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int s1, s2;
	int e1, e2;

	cin >> N >> M;

	for(int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	cin >> H >> W;
	cin >> s1 >> s2 >> e1 >> e2;

	cout << Bfs(s1, s2, e1, e2);

}

 

---

시행착오

간단한 문제인 줄 알았는데,
코드를 깔끔하게 잘려다 보니 오히려 머리가 꼬여서 오래 걸려버린 이상한 문제

그냥 주먹구구식으로 안 짜려고 하다 보니 오히려 더 독이 된 것 같다.

이렇게 풀면 쉽게 풀릴 것을.. 왜 안 풀었을까..