탈출 3055-c++

이번문제는 bfs를 활용한 문제입니다.
핵심은.

1. 물과 고슴도치가 1개가 아니다.
2. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.
3. q.size()를 미리 밖으로 빼두어야한다.

이3가지가 핵심이 되겠습니다. 하나하나 설명을 해보자면
어? 물은 1개가 아닌건 알겠는데 고슴도치는 1개아닌가? 싶을 수 있습니다.
코드르보면,
//고슴도치를 옴기는 code

int qsize = q.size();
		for (int k = 0; k < qsize; k++) {
			int cnt = q.front().first;
			int x = q.front().second.first;
			int y = q.front().second.second;
			q.pop();
			if (map[x][y] == 'D') {
				cout << cnt;
				t++;
				break;
			}
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx >= 0 && nx < R && ny >= 0 && ny < C && !check[nx][ny] && map[nx][ny] != 'X' && map[nx][ny] != '*') {
					q.push({ cnt + 1,{nx,ny} });
					check[nx][ny] = true;
				}
			}

q에는 고슴도치의 위치가 들어있습니다.
맨처음에 1,1에 고슴도치가 들어있다고칩시다. 만약에 4방향에 물과 바위가 없다면,
q에는 0,1 1,2 1,0, 2,1 이렇게 4방향에 고슴도치가 위치할 것 입니다.
그래서 다음 while문으로 들어왔을때, 미리 고슴도치의 size를 찾아서
1개씩 q에서 빼서 다시 4방향을 검사해서 넣어줘야합니다.
만약 q.size()라고 설정한다면, q가 계속 늘어나니까 원하는 맨처음 4개의 고슴도치 위치보다 더 많이 검사하게됩니다.

두번째로는, 고슴도치가 물에 잠길 수 있으므로, 물을 먼저 확장시켜야합니다.

while (!q.empty()) {
		flush();
		int qsize = q.size();
        ...

고로 flush로 물을 먼저 확장한 후에 그후에 고슴도치 위치를 확장 시켰습니다.

정답코드

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

char map[51][51] = {};
bool check[51][51] = {};
int R, C;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
bool checkwater[51][51] = {};
int t = 0;
int sx, sy;
queue <pair<int, int>> water;
int Dx, Dy;

void flush() {
	int s = water.size();
	for (int i = 0; i < s; i++) {
		int x = water.front().first;
		int y = water.front().second;
		water.pop();
		for (int j = 0; j< 4; j++) {
			int nx = x + dx[j];
			int ny = y + dy[j];
			if (nx >= 0 && nx < R && ny >= 0 && ny < C && !checkwater[nx][ny] && map[nx][ny] != 'D' && map[nx][ny] != 'X') {
				map[nx][ny] = '*';
				checkwater[nx][ny] = true;
				water.push({ nx,ny });
			}
		}
	}
}


void bfs() {
	queue<pair<int, pair<int, int>>>q;
	q.push({ 0,{sx,sy} });
	check[sx][sy] = true;
	while (!q.empty()) {
		flush();
		int qsize = q.size();
		for (int k = 0; k < qsize; k++) {
			int cnt = q.front().first;
			int x = q.front().second.first;
			int y = q.front().second.second;
			q.pop();
			if (map[x][y] == 'D') {
				cout << cnt;
				t++;
				break;
			}
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx >= 0 && nx < R && ny >= 0 && ny < C && !check[nx][ny] && map[nx][ny] != 'X' && map[nx][ny] != '*') {
					q.push({ cnt + 1,{nx,ny} });
					check[nx][ny] = true;
				}
			}
		}
	}
	if (t == 0) {
		cout << "KAKTUS";
	}
}

int main() {
	cin >> R >> C;
	//map받기
	for (int i = 0; i < R; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < temp.size(); j++) {
			if (temp[j] == 'S') {
				sx=i;
				sy=j;
			}
			else if (temp[j] == '*') {
				water.push({ i,j });
				checkwater[i][j] = true;
			}
			else if (temp[j] == 'D') {
				Dx=i;
				Dy=j;
			}
			map[i][j] = temp[j];
		}
	}

	//bfs
	bfs();
	return 0;
}

난이도 하