[C++]BOJ 2644 - 탈출

돌이 ‘X’라는 말을 못봐서 틀렸다. 이런거 못보고 지나쳐서 틀렸을때는 매우 화난다. 그리고 이런곳에서 틀릴거라곤 상상도 못하기 때문에 해결하는데 시간도 오래걸린다.

아무튼 bfs다.
한칸씩 확장해나가기 위해 큐 사이즈를 기준으로 while을 번갈아가며 돌린다.
비버가 굴에 도착하면 확장시킨 횟수를 출력한다.
비버가 굴로 못들어가면 “선인장”을 출력한다.

#include <iostream>
#include <queue>
using namespace std;
int r, c, cx, cy, xx, yy, gs, wss, dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0}, ans;
char arr[52][52];
queue<int> wx, wy, gx, gy;
int main() {
	cin >> r >> c;
	for(int i = 0; i < r; i++) {
		scanf("%s", &arr[i]);
		for(int j = 0; j < c; j++)
			if(arr[i][j] == 'S') gx.push(j), gy.push(i);
			else if(arr[i][j] == '*') wx.push(j), wy.push(i);
	}
	while(!gx.empty()) {
		wss = wx.size(); gs = gx.size();
		while(wss--) {
			cx = wx.front(); wx.pop();
			cy = wy.front(); wy.pop();
			for(int i = 0; i < 4; i++) {
				xx = cx + dx[i]; yy = cy + dy[i];
				if(xx >= c || yy >= r || xx < 0 || yy < 0 || arr[yy][xx] != '.') continue;
				wx.push(xx), wy.push(yy); arr[yy][xx] = '*';
			}
		}
		while(gs--) {
			cx = gx.front(); gx.pop();
			cy = gy.front(); gy.pop();
			if(arr[cy][cx] == 'D') {
				cout << ans;
				return 0;
			}
			for(int i = 0; i < 4; i++) {
				xx = cx + dx[i]; yy = cy + dy[i];
				if(xx >= c || yy >= r || xx < 0 || yy < 0 || arr[yy][xx] == 'S' || arr[yy][xx] == '*' || arr[yy][xx] == 'X') continue;
				gx.push(xx), gy.push(yy);
				if(arr[yy][xx] != 'D') arr[yy][xx] = 'S';
			}
		}
		ans++;
	}
	cout << "KAKTUS";
}