[G4] 백준 16973번 직사각형 탈출 C++ 너비 우선 탐색

리뷰

 

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

맵에서 직사각형을 움직이며 목적지 까지 이동이 가능한지를 구하는 문제

 

 

전역 변수

• n, m : 맵의 세로/가로 크기를 저장할 변수
• lst : 맵 정보를 입력 받고 저장할 2차원 배열
• v : 방문 정부를 체크하기 위한 2차원 배열
• h, w : 직사각형의 세로/가로 크기를 저장할 변수
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 현재 위치와 누적 소요시간을 정의할 구조체

 

함수

1. bfs

int bfs(int sx, int sy, int ex, int ey) {
	queue<Pos> q;
	q.push({ sx, sy, 0 });
	v[sx][sy] = true;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t;
		if (cx == ex && cy == ey) {
			//cout << "result = cx:" << cx << " cy:" << cy << " ct:" << ct << "\n";
			return ct;
		}
		//cout << "cx:" << cx << " cy:" << cy << " ct:" << ct << "\n";

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;

			if (0 <= nx && nx + h <= n && 0 <= ny && ny + w <= m && !v[nx][ny]) {
				v[nx][ny] = true;

				bool flag = true;
				if (i == 0) {
					for (int i = 0; i < w; ++i) {
						if (lst[nx + h - 1][ny + i]) {
							flag = false;
							break;
						}
					}
				}
				else if (i == 1) {
					for (int i = 0; i < w; ++i) {
						if (lst[nx][ny + i]) {
							flag = false;
							break;
						}
					}
				}
				else if (i == 2) {
					for (int i = 0; i < h; ++i) {
						if (lst[nx + i][ny + w - 1]) {
							flag = false;
							break;
						}
					}
				}
				else {
					for (int i = 0; i < h; ++i) {
						if (lst[nx + i][ny]) {
							flag = false;
							break;
						}
					}
				}

				if (flag) q.push({ nx, ny, nt });
			}
		}
	}
	return -1;
}

 

너비 우선 탐색을 통해 사각형을 이동하여 시작 지점부터 목표 지점까지 소요되는 시간을 구하는 함수

 

 

문제풀이

1. n, m값을 입력 받고, n*m크기의 맵 정보를 배열 lst에 입력 받아준다.
2. 변수 sx, sy, ex, ey를 초기화 하고, h, w, sx, sy, ex, ey에 직사각형의 크기와 출발, 목표 위치를 입력 받아준다.
3. bfs함수에 sx, sy, ex, ey를 전위감소 시켜 매개변수로 전달하여 함수를 호출해 준다.
4. Pos타입의 큐 q를 초기화 하고, 초기 위치 sx, sy와 누적 소요시간 0을 push해준다.
5. v배열에 시작 위치 sx, sy를 방문처리하고, q가 빌때까지 while루프를 수행해 준다.
6. 매 루프마다 요소를 한개씩 꺼내어 주고, 변수 cx, cy, ct에 현재 위치와 누적 소요시간을 파싱해 준다.
7. 기저 조건으로 현재 위치가 목표 위치라면 ct를 리턴해 준다.
8. 4방향 탐색을 진행하고, 변수 nx, ny에 이동할 위치를 저장하고 nt에 ct + 1을 저장해 준다.
9. 이동할 위치를 기준으로 사각형이 맵 범위 안에 있고 방문하지 않은 경우 이동을 진행한다.
10. 이동 후 방문처리를 하고, 변수 flag를 초깃값 true로 초기화 해준다.
11. 이동할 방향에 따라 이동할 변에 벽이 있는지를 체크해 주고, 있다면 flag를 false로 변경 후 break처리해 준다.
12. while루프 내에서 기저조건에 도달하지 못한 경우 -1을 리턴해 준다.
13. bfs함수의 리턴 결과값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 입력으로 주어진 직사각형은 격자판을 벗어나지 않고, 직사각형이 놓여 있는 칸에는 벽이 없다.
• 이로 인해 사각형 전체를 체크할 필요 없이 이동할 방향에 따른 변만 벽이 닿는지 체크해 주어도 된다.

 

정답 코드

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

int n, m;
int lst[1000][1000];
bool v[1000][1000];
int h, w;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y, t;
};

int bfs(int sx, int sy, int ex, int ey) {
	queue<Pos> q;
	q.push({ sx, sy, 0 });
	v[sx][sy] = true;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t;
		if (cx == ex && cy == ey) {
			//cout << "result = cx:" << cx << " cy:" << cy << " ct:" << ct << "\n";
			return ct;
		}
		//cout << "cx:" << cx << " cy:" << cy << " ct:" << ct << "\n";

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;

			if (0 <= nx && nx + h <= n && 0 <= ny && ny + w <= m && !v[nx][ny]) {
				v[nx][ny] = true;

				bool flag = true;
				if (i == 0) {
					for (int i = 0; i < w; ++i) {
						if (lst[nx + h - 1][ny + i]) {
							flag = false;
							break;
						}
					}
				}
				else if (i == 1) {
					for (int i = 0; i < w; ++i) {
						if (lst[nx][ny + i]) {
							flag = false;
							break;
						}
					}
				}
				else if (i == 2) {
					for (int i = 0; i < h; ++i) {
						if (lst[nx + i][ny + w - 1]) {
							flag = false;
							break;
						}
					}
				}
				else {
					for (int i = 0; i < h; ++i) {
						if (lst[nx + i][ny]) {
							flag = false;
							break;
						}
					}
				}

				if (flag) q.push({ nx, ny, nt });
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> lst[i][j];
		}
	}

	int sx, sy, ex, ey;
	cin >> h >> w >> sx >> sy >> ex >> ey;
	cout << bfs(--sx, --sy, --ex, --ey);
}