[백준/BOJ] 백준 3055번 : 탈출

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

3055번: 탈출

물들이 board에서 확장하는 함수를 만들었고, start에서 dest으로 가는 가장 빠른 시간을 구하는 함수를 만들었다.

 

코드

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

int r, c;
vector<string> board;
int dx_dy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int discoverd[50][50];
int depth[50][50];
queue<pair<int, int>> water;

//물들의 확장
void waterSpread()
{
	int water_size = water.size();

	//현재시간에 water큐에 들어 있는 물들만 확장을 한다(확장으로 인해 생성되는 물들은 다음을 위해 큐에 저장하는것)
	//그리고 현재시점에 확장한 물들은 이제 확장해도 의미가 없으므로 pop한다 
	for (int i = 0; i < water_size; i++)
	{
		pair<int, int> here_water = water.front();
		water.pop();

		for (int j = 0; j < 4; j++)
		{
			pair<int, int> there_water = make_pair(here_water.first + dx_dy[j][0], here_water.second + dx_dy[j][1]);

			if (there_water.first >= 0 && there_water.first < r && there_water.second >= 0 && there_water.second < c && board[there_water.first][there_water.second] == '.')
			{
				board[there_water.first][there_water.second] = '*';
				water.push(there_water);
			}
		}
	}

}

int Solve(pair<int, int> start, pair<int, int> dest)
{
	memset(discoverd, 0, sizeof(discoverd));

	discoverd[start.first][start.second] = 1;
	depth[start.first][start.second] = 0;

	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		int q_size;
		q_size = q.size(); //큐 사이즈를 저장한다

		//물이 확장한다
		waterSpread();

		for (int i = 0; i < q_size; i++)
		{
			pair<int, int> here = q.front();
			q.pop();

			//목적지에 도착 했을때
			if (here.first == dest.first && here.second == dest.second)
				return depth[here.first][here.second];

			for (int i = 0; i < 4; i++)
			{
				pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
				if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && board[there.first][there.second] != 'X' && board[there.first][there.second] != '*' && discoverd[there.first][there.second] == 0)
				{
					discoverd[there.first][there.second] = 1;
					depth[there.first][there.second] = depth[here.first][here.second] + 1;

					q.push(there);
				}
			}
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;
	pair<int, int> start;
	pair<int, int> dest;
	int result;

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		cin >> temp;
		board.push_back(temp);

		for (int j = 0; j < c; j++)
		{
			//고슴도치의 위치(시작위치)라면
			//위치를 저장하고, 그 부분은 비어있는 곳과 같이 '.'로 저장한다
			if (board[i][j] == 'S')
			{
				start = make_pair(i, j);
				board[i][j] = '.';
			}

			else if (board[i][j] == 'D')
				dest = make_pair(i, j);

			//물의 위치들을 큐에 저장한다
			else if (board[i][j] == '*')
				water.push(make_pair(i, j));
		}
	}

	result = Solve(start, dest);

	if (result == -1)
		cout << "KAKTUS";
	else
		cout << result;

	return 0;
}