BOJ 백준 3055 탈출

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

3055번: 탈출

문제 풀이 )

 

    1. 'D'와 'S', 즉 비버 굴과 고슴도치의 시작 지점은 하나씩만 주어진다고 되어 있지만, 물이나 돌은 그런 표현이 없다.

 

        즉, 물이나 돌은 없을 수도, 여러 개가 나올 수 있다는 것을 의미한다.

 

        R과 C가 50보다 작거나 같은 자연수란 것은, R과 C 둘 다 1일 수 있을 것 같은데, 테스트 해보니 0이나

 

        갈 수 없다는 KAKTUS를 출력해주어도 둘 다 맞게 나온다.

 

        평범한 BFS문제와 다른 점은, '물'이 시간이 지날때마다 번지는 상황이 있다는 것이다.

 

        고슴도치는 물이 다음에 찰 장소에는 이동하지 못한다는 조건이 있다.

 

        따라서 맵 크기만큼의 배열에 BFS를 이용하여 물이 도달할 시간들을 저장해준 뒤,

 

        고슴도치의 BFS 조건에 물의 시간을 추가해주어, 물에 잠길 장소인 경우 탐색을 하지 않도록 해주면 된다.

 

소스 코드

#include <cstdio>
#include <queue>

using namespace std;

const int SIZE = 55;

int waterDist[SIZE][SIZE] = { 0 };
int xDir[4] = { 1,-1,0,0 };
int yDir[4] = { 0,0,1,-1 };
int r, c;
int ans = -1;

char map[SIZE][SIZE] = { 0 };
bool visit[SIZE][SIZE] = { 0 };

pair<int, int> startPos;
pair<int, int> endPos;
queue< pair<int, int> > q_water;

void Water_BFS()
{
	int _qSize = q_water.size();
	for (int i = 0; i < _qSize; ++i)
		waterDist[q_water.front().first][q_water.front().second] = 1;

	int nPath = 1;

	while (!q_water.empty())
	{
		int qSize = q_water.size();

		for (int i = 0; i < qSize; ++i)
		{
			int cur_x = q_water.front().first;
			int cur_y = q_water.front().second;
			q_water.pop();

			for (int j = 0; j < 4; ++j)
			{
				int next_x = cur_x + xDir[j];
				int next_y = cur_y + yDir[j];

				// 맵 밖
				if (next_x < 0 || next_y < 0 || next_x >=r || next_y >= c) continue;
				// 이미 체크한 장소
				if (waterDist[next_x][next_y]) continue;
				// 돌 및 비버의 소굴
				if (map[next_x][next_y] == 'X') continue;
				if (map[next_x][next_y] == 'D') continue;

				q_water.push({ next_x, next_y });
				waterDist[next_x][next_y] = nPath;
			}
		}
		++nPath;
	}
}

void Hedgehog_BFS()
{
	queue< pair<int, int> > q;
	q.push({ startPos.first, startPos.second });
	visit[startPos.first][startPos.second] = true;
	int nPath = 0;

	while (!q.empty())
	{
		int qSize = q.size();
		for (int i = 0; i < qSize; ++i)
		{
			int cur_x = q.front().first;
			int cur_y = q.front().second;
			q.pop();

			if (cur_x == endPos.first && cur_y == endPos.second)
			{
				ans = nPath;
				return;
			}

			for (int j = 0; j < 4; ++j)
			{
				int next_x = cur_x + xDir[j];
				int next_y = cur_y + yDir[j];

				if (next_x < 0 || next_y < 0 || next_x >= r || next_y >= c) continue;
				if (visit[next_x][next_y]) continue;
				if (map[next_x][next_y] == 'X') continue;
				if (waterDist[next_x][next_y] != 0 &&
					waterDist[next_x][next_y] - (nPath + 1) <= 0)
					continue;

				q.push({ next_x, next_y });
				visit[next_x][next_y] = true;
			}
		}
		++nPath;
	}
}

void Solution()
{
	// 물이 맵을 덮칠 시간을 타일 별로 계산
	Water_BFS();
	Hedgehog_BFS();
}

int main()
{
	scanf("%d %d", &r, &c);
	for (int i = 0; i < r; ++i)
	{
		scanf(" %s", map[i]);
		for (int j = 0; j < c; ++j)
		{
			// 고슴도치
			if (map[i][j] == 'S')
			{
				startPos.first = i;
				startPos.second = j;
			}

			// 비버의 굴
			else if (map[i][j] == 'D')
			{
				endPos.first = i;
				endPos.second = j;
			}

			// 물의 시작점
			else if (map[i][j] == '*')
				q_water.push({ i, j });
		}
	}

	Solution();
	if (ans == -1) printf("KAKTUS\n");
	else printf("%d\n", ans);
	
	return 0;
}