[BOJ] 백준 3055번 탈출 C++

문제

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

3055번: 탈출

풀이

백준에 있는 불! 문제랑 비슷하다.

물에 대한 BFS와 비버에 대한 BFS를 각각 돌려주어 풀었다.

먼저 물에 대한 BFS를 돌아 물이 차는 시간과 방문 여부를 체크해주었다. 이후에 비버에 대한 BFS를 돌며

비버가 도착할 시간이 물이 차는 시간보다 작아야만 비버가 움직일 수 있기 때문에 조건을 달아주어 만족하는 경우에만 비버가 방문할 수 있게하는 것이 핵심이다.

하지만 예외상황이 발생할 수 있다. 돌 때문에 물이 찰 수 없는 지역은 항상 -1이기 때문에 비버가 도착할 수 없는 상황이 생기게되어 앞서 물의 방문여부를 체크한 것을 바탕으로 물이 방문하지 않았고, 비버가 갈 수 있는 곳이면 물의 시간과 상관 없이 탐색을 할 수 있도록 처리해주었고, 물이 방문했다면 물이 차는 시간보다 작아야만 를 탐색을 할 수 있도록 해주었다.

그렇게 탐색을 하다 동굴을 만나면 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력해준다. 동굴에 갈 수 없으면(While문을 탈출한 경우) "KAKTUS"를 출력해주고 프로그램을 종료해주었다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;

int n, m, waterCnt;
char board[51][51];
int distWater[51][51];
int distBeaver[51][51];
bool visited[51][51];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> waterQ;
queue<pair<int, int>> beaverQ;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			distWater[i][j] = -1;
			distBeaver[i][j] = -1;
			visited[i][j] = false;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char c;
			cin >> c;
			board[i][j] = c;

			if (c == '*')
			{
				waterQ.push({ i,j });
				distWater[i][j] = 0;
				visited[i][j] = true;
			}
			if (c == 'S')
			{
				beaverQ.push({ i,j });
				distBeaver[i][j] = 0;
			}
		}
	}

	while (!waterQ.empty())
	{
		auto cur = waterQ.front();
		waterQ.pop();
		
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.x + dx[dir];
			int ny = cur.y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			{
				continue;
			}
			else
			{
				if (board[nx][ny] != 'X' && distWater[nx][ny] == -1 && board[nx][ny] != 'D' && board[nx][ny] != '*')
				{
					distWater[nx][ny] = distWater[cur.x][cur.y] + 1;
					waterQ.push({ nx, ny });
					visited[nx][ny] = true;
				}
			}
		}
	}

	while (!beaverQ.empty())
	{
		auto cur = beaverQ.front();
		beaverQ.pop();

		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.x + dx[dir];
			int ny = cur.y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m)
			{
				continue;
			}
			else
			{
				if (board[nx][ny] == 'D')
				{
					distBeaver[nx][ny] = distBeaver[cur.x][cur.y] + 1;
					cout << distBeaver[nx][ny];
					return 0;
				}
				if (visited[nx][ny] == false && distBeaver[nx][ny] == -1 && board[nx][ny] != 'X')
				{
					distBeaver[nx][ny] = distBeaver[cur.x][cur.y] + 1;
					beaverQ.push({ nx, ny });
					continue;
				}
				if (board[nx][ny] != 'X' && distBeaver[nx][ny] == -1 && distBeaver[cur.x][cur.y] + 1 < distWater[nx][ny])
				{
					distBeaver[nx][ny] = distBeaver[cur.x][cur.y] + 1;
					beaverQ.push({ nx, ny });
				}
			}

		}
	}

	cout << "KAKTUS";
}