[G3] 백준 14442번 벽 부수고 이동하기 2 C++ 너비 우선 탐색, 우선순위 큐

리뷰

 

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

어우 AC를 받긴 했는데 메모리는 둘째 치고 시간이 꽤나 올래걸려서 놀랐다.

 

유사 문제

[G2] 백준 16946번 벽 부수고 이동하기 4 C++ BFS, FloodFill, 너비 우선 탐색

 

 

전역 변수

• n : 맵의 세로 길이를 저장하기 위한 변수
• m : 맵의 가로 길이를 저장하기 위한 변수
• k : 부술 수 있는 벽의 개수를 저장하기 위한 변수
• Pos : 시뮬레이션 시 사용하기 위한 구조체, x, y좌표와 걸린 시간, 부순 벽의 수를 기록하고 시간 기준 오름차순 정렬
• lst : 맵 정보를 입력 받기 위한 문자열 타입의 배열
• v : 방문 정보를 체크하기 위한 정수형 3차 배열
• dx, dy : 4방향 탐색을 하기 위한 방향 배열

 

함수

1. bfs

int bfs()

 

시뮬레이션을 통해 시작점에서 도착점까지의 최단 거리를 구하기 위한 함수

1. Pos타입의 우선순위 큐 pq를 초기화 하고 0, 0좌표와 시작 시간1, 벽 부순 회수 0을 push해준다.
2. 초기 위치 0, 0과 벽을 부순 회수 0을 v배열을 통해 방문처리를 진행해 준다.
3. pq가 빌 때 까지 while루프를 돌며 매 루프마다 요소 한개씩을 꺼내어 준다.
4. 현재 x, y좌표를 cx, cy, 현재까지 걸린 시간을 ct, 현재 벽을 부순 횟수를 cu로 파싱해 준다.
5. 기저 조건으로 만약 cx, cy가 각각 n - 1, m - 1이라면 도착점에 도달한 것이므로 ct를 리턴해 준다.
6. 4방향 탐색을 진행하고 이동할 위치가 맵의 범위 안이라면 이동을 진행해 준다.
7. 맵 상에서 '0'인 위치라면 방문처리가 되지 않은 경우 이동을 진행하고 방문 처리 후 pq에 시간을 1늘려 push해준다.
8. '1'이라면 cu가 k보다 작고, cu + 1한 이동 위치가 방문 처리가 되어있지 않은 경우 이동을 진행한다.
9. cu + 1한 이동 위치에 방문처리 후 pq에 이동 위치, 시간과 벽 부순횟수를 1늘려 push해준다.
10. while루프동안 기저조건에 도달하지 못한 경우 -1을 리턴해 준다.

 

문제풀이

1. n, m, k값을 입력 받아주고 n개의 문자열을 lst배열에 입력 받아준다.
2. bfs함수를 호출하고 리턴값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

"시작하는 칸과 끝나는 칸도 포함해서 센다."라는 조건이 있으니 시작 시간을 1로 세팅해야 한다.

 

 

정답 코드

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

int n, m, k;
struct Pos {
	int x, y, t, u;
	bool operator<(const Pos& other) const {
		return t > other.t;
	}
};
string lst[1000];
bool v[11][1000][1000];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int bfs() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 1, 0 });
	v[0][0][0] = 1;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t, cu = pos.u;
		if (cx == n - 1 && cy == m - 1) return ct;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (lst[nx][ny] == '0') {
					if (v[cu][nx][ny]) continue;
					v[cu][nx][ny] = 1;
					pq.push({ nx, ny, ct + 1, cu });
				}
				else {
					if (cu == k) continue;
					if (v[cu + 1][nx][ny]) continue;
					v[cu + 1][nx][ny] = 1;
					pq.push({ nx, ny, ct + 1, cu + 1 });
				}
			}
		}
	}
	return -1;
}

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

	cin >> n >> m >> k;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	cout << bfs();
}