[G4] 백준 2194번 유닛 이동시키기 C++ 너비 우선 탐색

리뷰

 

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

2차원 맵에서 출발지에서 도착지까지 사각형이 이동하는 최단 시간을 구하는 문제

 

 

전역 변수

• n, m : 맵의 세로/가로 길이를 저장할 변수
• a, b : 사각형의 세로/가로 길이를 저장할 변수
• k : 장애물의 개수를 저장할 변수
• lst : 장애물의 위치를 표기하기 위한 배열
• v : 방문 여부를 확인하기 위한 배열
• 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) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;
			if (0 < nx && nx + a - 1 <= n && 0 < ny && ny + b - 1 <= m && !v[nx][ny]) {
				v[nx][ny] = true;
				bool move = true;

				if (i == 0) {
					for (int j = 0; j < b; ++j) {
						if (lst[nx + a - 1][ny + j]) {
							move = false;
							break;
						}
					}
				}
				else if (i == 1) {
					for (int j = 0; j < b; ++j) {
						if (lst[nx][ny + j]) {
							move = false;
							break;
						}
					}
				}
				else if (i == 2) {
					for (int j = 0; j < a; ++j) {
						if (lst[nx + j][ny + b - 1]) {
							move = false;
							break;
						}
					}
				}
				else {
					for (int j = 0; j < a; ++j) {
						if (lst[nx + j][ny]) {
							move = false;
							break;
						}
					}
				}

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

 

장애물이 없는 경로에서 사각형의 이동 가능 여부와 출발지부터 목적지까지 도달하기 까지의 소요 시간을 구하는 함수

 

 

문제풀이

1. 전역 변수 n, m, a, b, k에 값을 입력 받고, k개의 장애물의 좌표를 입력받아 lst배열에 표시해 준다.
2. 변수 sx, sy, ex, ey에 출발 좌표와 목표 좌표를 입력 받고, bfs함수에 매개변수로 전달하여 호출한다.
3. Pos타입의 큐 q를 초기화 하고, 초기 위치 sx, sy와 소요시간 0을 push해준다.
4. v배열에 시작 위치의 좌표를 방문처리해준다.
5. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
6. 기저 조건으로 현재 위치가 도착 위치인 ex, ey에 도달한 경우 ct를 리턴해 준다.
7. 4방향 탐색을 시작하고, 사각형이 맵의 범위를 벗어나지 않으면서 방문하지 않았다면 이동을 진행한다.
8. 방문처리를 진행해 주고, 변수  move를 true로 초기화 시켜준다.
9. 각 이동 방향에 따라 이동한 면의 가장자리에 장애물이 없다면 q에 새로운 위치와 시간을 push해준다.
10. while루프가 종료될 때까지 기저조건에 도달하지 못했다면 -1을 리턴해준다.
11. bfs함수의 리턴값을 출력해 준다.

 

트러블 슈팅

1. 범위 체크를 할때 사각형의 우측 상단 꼭지점만 체크해 주어 Fail을 받았다.
2. 사각형의 모든 면이 범위 내에 존재하는지 체크해주어 문제를 해결하였다.
3. 상하 이동 시 이동한 행의 열을, 좌우 이동 시 이동한 열의 행을 체크해 주었으나 각각 왼쪽, 위쪽만 해주어 Fail을 받았다.
4. 상하좌우 이동 시 각각 위쪽, 아래쪽, 왼쪽, 오른쪽 면을 확인해 주어 AC를 받았다.

 

참고 사항

없음

 

 

정답 코드

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

int n, m, a, b, k;
bool lst[501][501];
bool v[501][501];
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) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nt = ct + 1;
			if (0 < nx && nx + a - 1 <= n && 0 < ny && ny + b - 1 <= m && !v[nx][ny]) {
				v[nx][ny] = true;
				bool move = true;

				if (i == 0) {
					for (int j = 0; j < b; ++j) {
						if (lst[nx + a - 1][ny + j]) {
							move = false;
							break;
						}
					}
				}
				else if (i == 1) {
					for (int j = 0; j < b; ++j) {
						if (lst[nx][ny + j]) {
							move = false;
							break;
						}
					}
				}
				else if (i == 2) {
					for (int j = 0; j < a; ++j) {
						if (lst[nx + j][ny + b - 1]) {
							move = false;
							break;
						}
					}
				}
				else {
					for (int j = 0; j < a; ++j) {
						if (lst[nx + j][ny]) {
							move = false;
							break;
						}
					}
				}

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

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

	cin >> n >> m >> a >> b >> k;
	while (k--) {
		int x, y; cin >> x >> y;
		lst[x][y] = true;
	}

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