[C++] 백준 3055번 탈출

BFS로 문제를 풀었습니다.

고슴도치가 한칸씩 이동해서 비버의 굴로 도착할 수 있는지
있다면 몇번만에 도착하는지와 없다면 KAKTUS를 출력해야합니다.
고슴도치가 한칸 이동할때마다 물이 상하좌우로 한칸씩 늘어나게 됩니다.

물을 한칸씩 증가시킨후 BFS를 통해서 갈 수 있는곳을
탐색하는 것을 반복하여서 문제를 풀었습니다.

 

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

int moveX[4] = { 0, 1, 0, -1};
int moveY[4] = { 1, 0, -1, 0};

int main(int argc, char* argv[])
{
	int n, m;
	int x, y;
	int a, b, c;
	int turn;
	int waterA, waterB, waterX, waterY;
	int waterCycle;
	int map[60][60];
	int visit[60][60];
	string s;
	queue<pair<pair<int, int>, int > >q;
	queue < pair<int, int> > water;
	cin >> n >> m;
	
	memset(map, 0, sizeof(map));

	for (int i = 1; i <= n; ++i) {
		cin >> s;
		for (int j = 1; j <= m; ++j) {
			if (s[j - 1] == 'X') {			// 돌 = 0
			map[i][j] = 0;
			}
			else if (s[j - 1] == '*') {		// 물 = 1;
				map[i][j] = 1;
				water.push(make_pair(i, j));
			}
			else if (s[j - 1] == '.') {		// 땅굴 = 2;
				map[i][j] = 2;
			}
			else if (s[j - 1] == 'D') {	// 비버 = 3;
				map[i][j] = 3;
			}
			else if (s[j - 1] == 'S') {	// 두더지;
				map[i][j] = 2;
				q.push(make_pair(make_pair(i, j), 0));
			}
		}
	}
	
	memset(visit, 0, sizeof(visit));
	turn = 1;

	while (!q.empty()) {
		a = q.front().first.first;
		b = q.front().first.second;
		c = q.front().second;
		visit[a][b] = 1;
		q.pop();
		
		if (turn != c) {
			turn = c;
			waterCycle = water.size();
			while (waterCycle--) {
				waterA = water.front().first;
				waterB = water.front().second;
				water.pop();
				for (int i = 0; i < 4; ++i) {
					waterX = waterA + moveX[i];
					waterY = waterB + moveY[i];
					if (map[waterX][waterY] == 2) {
						water.push(make_pair(waterX, waterY));
						map[waterX][waterY] = 1;
					}
				}
			}
		}

		for (int i = 0; i < 4; ++i) {
			x = moveX[i] + a;
			y = moveY[i] + b;
			if (map[x][y] == 3) {
				cout << c + 1 << endl;
				return 0;
			}
			if (!visit[x][y] && map[x][y] == 2) {
				q.push(make_pair(make_pair(x, y), c + 1));
				visit[x][y] = 1;
			}
		}
	}

	cout << "KAKTUS" << endl;

	return 0;
}