[G4] 백준 5427번 불 C++ 너비 우선 탐색, BFS, 우선순위 큐

리뷰

 

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

불을 피해 맵의 가장자리로 대피하는 시뮬레이션을 진행하는 문제 유사한 문제

유사한 문제로 불! 문제가 있다, 해당 문제는 아래에 풀이 내용이 있으니 공유한다.

백준 4179번 불! C++

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 변수
• w : 각 테스트 케이스의 맵의 가로 길이를 저장할 변수
• h : 각 테스트 케이스의 맵의 세로 길이를 저장할 변수
• lst : 각 테스트 케이스의 맵 정보를 입력 받아 저장할 문자열 타입의 배열
• v : 각 테스트 케이스의 맵 상에서 방문 여부를 체크하기 위한 정수형 2차 배열
• Pos : 시뮬레이션 시 사용할 x, y좌표와 진행 시간, 불인지 상근이인지 여부와 우선순위 큐 내에서 사용하기 위한 커스텀 operator 함수를 정의하기 위한 구조체, t기준으로 오름차순을 하고 동일하다면 불이 앞으로 오게 한다.

 

함수

1. bfs

int bfs(priority_queue<Pos>& pq)

 

상근이가 번지는 불을 피해 맵의 가장자리로 피할 수 있는지 여부를 체크하기 위한 함수

1. 매개변수로 불과 상근이의 초기 위치가 담긴 Pos타입 우선순위 큐pq를 전달 받는다.
2. pq안에 모든 요소가 빌 때까지 루프를 돌며 시뮬레이션을 진행해 준다.
3. 각 시뮬레이션 단계 마다 pq에서 요소를 빼내어 Pos타입의 변수 pos로 받아준다.
4. pos객체의 요소를 좌표를 각각 cx, cy 현재 시간을 ct, 불인지 상근이인지 여부를 id로 파싱해 준다.
5. 기저조건으로 만약 상근이의 위치가 가장자리에 도달했다면 ct를 리턴해 준다.
6. 4방향 탐색을 시작하고 아직 방문하지 않았으면서 맵 상에서 벽이 아니라면 로직을 수행해 준다.
7. 만약 현재가 상근이인데 이동하려는 위치가 불이라면 갈 수 없으므로 continue 처리해 준다.
8. 이동이 가능할 경우 이동한 위치에 방문 표시 후 맵 상에서 해당 좌표를 id로 변경해 준다.
9. 이후 이동한 위치의 좌표와 진행된 시간, id값을 pq에 push해준다.
10. 만약 루프가 종료될 때 까지 기저조건에 도달하지 못했다면 -1를 리턴해 준다.

 

문제풀이

1. t값을 입력 받고 t번의 테스트 케이스를 루프를 돌며 실행해 준다.
2. 각 테스트 케이스 마다 w, h값을 입력 받고, Pos타입의 우선순위 큐 pq를 초기화 해준다.
3. memset메서드를 통해 이전 케이스에 사용한 방문 배열을 0으로 초기화 해준다.
4. h * w크기의 맵 정보를 입력 받고, 만약 상근이('@')거나 불('*')이라면 해당 위치를 방문표시 후 pq에 push 해준다.
5. bfs에 pq를 매개변수로 전달하고 받은 리턴값을 정수형 변수 result에 저장해 준다.
6. 만약 result의 값이 -1이라면 "IMPOSSIBLE"을, 아니라면 result값을 출력 후 줄바꿈을 수행해 준다.
7. 모든 테스트 케이스가 종료될 때 까지 위 로직을 반복해 준다.

 

참고 사항

"상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다."

문제에서 이미 힌트를 주고 있다, 이걸 보고 나서 상근이 이동 전에 불 부터 이동해야 겠다는 생각이 들었다.

단, 불이 이동했을 때의 위치에 상근이가 있는 것은 아무런 문제가 없다.

 

 

정답 코드

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

int t, w, h;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
string lst[1000];
int v[1000][1000];
struct Pos {
	int x, y, t;
	char id;
	bool operator<(const Pos& other) const {
		if (t == other.t) {
			if (id == other.id) return false;
			return id == '@';
		}
		return t > other.t;
	}
};


int bfs(priority_queue<Pos>& pq) {
	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, ct = pos.t;
		char id = pos.id;
		if (id == '@') {
			if (cx == 0 || cx == h - 1 || cy == 0 || cy == w - 1) 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 < h && 0 <= ny && ny < w && !v[nx][ny] && lst[nx][ny] != '#') {
				if (id == '@' && lst[nx][ny] == '*') continue;
				v[nx][ny] = 1;
				lst[nx][ny] = id;
				pq.push({ nx, ny, nt, id });
			}
		}
	}
	return -1;
}

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

	cin >> t;
	while (t--) {
		cin >> w >> h;

		priority_queue<Pos> pq;
		memset(v, 0, sizeof(v));
		for (int i = 0; i < h; ++i) {
			cin >> lst[i];
			for (int j = 0; j < w; ++j) {
				if (lst[i][j] == '@' || lst[i][j] == '*') {
					v[i][j] = 1;
					pq.push({ i, j, 1, lst[i][j] });
				}
			}
		}
		int result = bfs(pq);
		if (result == -1) cout << "IMPOSSIBLE\n";
		else cout << result << "\n";
	}

	
}