백준 3055번 탈출 C++ BFS, 너비 우선 탐색

리뷰

시간마다 번지는 물을 피해 S에서 D로 이동하는 문제, 첫번째는 방문배열을 조건에 넣어 주지 않았고, 두번째는 'X'가 있는지 몰랐다... 쉬워보이는 문제더라도 문제를 잘 읽어야겠다.

 

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

 

문제 풀이

1. r과 c값을 가져오고 string으로 이루어진 맵을 입력 받아준다.
2. 문자열의 각 문자를 참고하여 S일 경우와 D일 경우 위치 좌표를 저장해 둔다.
3. 만약 *일 경우 물이 번짐을 체크해야 하므로 별도로 준비해둔 큐에 저장해 준다.
4. bfs를 시작하고, 시작 위치를 미리 준비해두었던 큐에 추가해 준 뒤 탐색을 시작한다.
5. 만약 물이 맵에 존재한다면 이미 큐에 저장되어 있을 것이다, 큐에서 pop한 char이 *라면 다음 이동방향이 .일 경우 *로 변경해 준다.
6. 만약 현재 char이 S라면 다음 좌표가 *이거나 X인 경우에는 이동하지 못하게 한다, D일 경우 시간을 리턴해 준다.
7. while이 완료될 때까지 D에 도달하지 못했다면, -1을 리턴해 준다.
8. bfs의 리턴값이 -1일 경우 KAKTUS를 출력, 아니라면 bfs의 리턴값을 출력해 주면 된다.

 

참고 사항

구조체를 활용하여 큐에 저장된 현재 값이 무엇인지 판단해 주면 쉽게 풀 수 있다.

 

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;

string lst[50];
int v[50][50] = { 0, };
int r, c, sx, sy, ex, ey;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y;
	char z;
};

queue<Pos> q;

int bfs() {
	q.push({ sx, sy, 'S' });
	v[sx][sy] = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, cz = pos.z;
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < r && 0 <= ny && ny < c && !v[nx][ny] && lst[nx][ny] != '*' && lst[nx][ny] != 'X') {
				if (cz == '*' && lst[nx][ny] == '.') {
					lst[nx][ny] = '*';
					q.push({ nx, ny, '*' });
				}
				else if (cz == 'S' && lst[nx][ny] == 'D') return v[cx][cy];
				else if (cz == 'S' && lst[nx][ny] != '*') {
					v[nx][ny] = v[cx][cy] + 1;
					q.push({ nx, ny, 'S' });
				}
			}
		}
	}
	return -1;
}

int main() {
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		cin >> lst[i];
		for (int j = 0; j < c; j++) {
			if (lst[i][j] == 'S') sx = i, sy = j;
			else if (lst[i][j] == 'D') ex = i, ey = j;
			else if (lst[i][j] == '*') q.push({ i, j, '*' });
		}
	}
	int ans = bfs();
	if (ans == -1) cout << "KAKTUS";
	else cout << ans;
}