백준 2665번 미로만들기 C++ BFS, 최단 경로, 우선순위 큐

리뷰

다익스트라 라고 보기엔 애매하고 그냥 우선순위 큐를 사용한 BFS 문제 라고 보면 될 것 같다.

 

문제 풀이

1. n값을 받고 1과 0이 붙어있길래 그냥 string으로 맵 정보를 받아주었다.
2. 방향 배열과 방문 처리를 할 배열을 초기화 해준다. 이때 방문 배열은 벽을 뚫은 횟수 기록용 3차 배열로 초기화
3. 거리, x좌표, y좌표를 인자로 갖는 구조체 Pos를 초기화 해준다.
4. 우선순위 큐에서 정렬용으로 사용할 compare 객체를 초기화 하고, 거리를 기준으로 오름차순으로 정렬해 준다.
5. bfs를 시작하고 0, 0부터 시작해 n-1, n-1에 도달 했을 경우 벽을 부순 횟수를 리턴해 주도록 한다.
6. 리턴값을 출력해 주면 된다.

 

참고 사항

bfs함수 내부 구조 상세 설명

1. Pos를 자료구조로 갖고, Pos 내 d를 오름차순으로 정렬하는 우선순위 큐 pq를 초기화 해준다.
2. 해당 pq에 현재 거리, 현재 x좌표, 현재 y좌표 0, 0, 0을 추가해 준다.
3. 방문 배열도 마찬가지로 현재 x좌표, 현재 y좌표, 현재 벽을 부순 횟수 v[0][0][0]을 1로 체크해 준다.
4. while루프를 실행하고 pq에 가장 top에 있는 인자를 가져오고 pop 해준다.
5. 만약 현재 위치가 종료 위치면 cd를 리턴한다, 우선순위 큐를 사용했으므로 이는 가장 적게 벽을 뚫고 온 것이 보장이 된다.
6. 이후에는 일반적인 bfs와 똑같다, 벽을 만났으면 벽을 만난 횟수를 올려주고, 방문 배열에서도 벽을 만난 횟수를 올려 준 후에 방문 처리를 해준다.
7. 만약 벽을 만나지 않았다면 그냥 nx, ny, cd를 그대로 방문처리 및 pq에 추가해 주면 된다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int n;
string lst[51];
int v[51][51][101];

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

struct Pos {
	int d, x, y;
};

struct compare {
	bool operator()(const Pos& left, const Pos& right) const {
		return left.d > right.d;
	}
};

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

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cd = pos.d;
		if (cx == n - 1 && cy == n - 1) return cd;

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				if (lst[nx][ny] == '0' && !v[nx][ny][cd + 1]) {
					v[nx][ny][cd + 1] = 1;
					pq.push({ cd + 1, nx, ny });
				}
				if (lst[nx][ny] == '1' && !v[nx][ny][cd]) {
					v[nx][ny][cd] = 1;
					pq.push({ cd, nx, ny });
				}
			}
		}
	}
}

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

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