[BFS] 탈출

예제 입력 1

3 3

D.*

...

.S.

예제 출력 1

3

예제 입력 2

3 3

D.*

...

..S

예제 출력

KAKTUS

예제 입력 3

3 6

D...*.

.X.X..

....S.

예제 출력 3

6

예제 입력 4

5 4

.D.*

....

..X.

S.*.

....

예제 출력 4

4

 

 

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

3055번: 탈출

- 먼저 물을 싹다 큐에 넣고 BFS돌려서 물이 차는 시간을 계산한다.

- 그 다음 고슴도치를 큐에 넣고 BFS 돌려서, 빈칸인 경우 물이 차는 시간보다 현재 시간이 더 빠른경우 이동 가능하도록 처리하면 된다.

- 물이 차는 시간을 -1로 초기화 했었는데, 이 조건을 따로 처리를 안해서 물이 없는 빈칸이라도 -1로 되어버려 이동 못해서 좀 헤맸었음.

 

#include <stdio.h>

constexpr int MAX_SIZE = 50;
constexpr int MAX_QUEUE_SIZE = 1000;

int R, C;

char map[MAX_SIZE + 1][MAX_SIZE + 1];

bool goSeum_dist[MAX_SIZE + 1][MAX_SIZE + 1];
bool water_dist[MAX_SIZE + 1][MAX_SIZE + 1];

int dR[] = { -1, 1, 0, 0 };
int dC[] = { 0, 0, -1, 1 };

class Point
{
public:
	int r;
	int c;

	Point() { r = c = 0; }
	Point(int r, int c) : r(r), c(c) {}

	bool isInBoundary(int R, int C)
	{
		return (r >= 0) && (r < R) && (c >= 0) && (c < C);
	}

	bool operator==(Point other)
	{
		return (r == other.r) && (c == other.c);
	}
};

template <typename T>
class Queue
{
private:
	int front;
	int rear;
	T items[MAX_QUEUE_SIZE];

public:
	Queue() { front = rear = 0; }

	void push(T item)
	{
		items[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = items[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty() { return front == rear; }

	void init() { front = rear = 0; }
};
Queue<Point> q;
Point goseum;
Point target;

int dist_water[MAX_SIZE][MAX_SIZE];
int dist_goseum[MAX_SIZE][MAX_SIZE];

int main(void)
{
	scanf("%d %d", &R, &C);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			dist_water[i][j] = -1;
			dist_goseum[i][j] = -1;

			while (true)
			{
				scanf("%c", &map[i][j]);

				if (map[i][j] != '\n') break;
			}

			if (map[i][j] == '*') // 물
			{
				Point water(i, j);
				dist_water[i][j] = 0;
				q.push(water);
			}

			if (map[i][j] == 'S')
			{
				goseum.r = i;
				goseum.c = j;
			}
			
			if (map[i][j] == 'D')
			{
				target.r = i;
				target.c = j;
			}
		}
	}

	// 물 이동
	while (!q.isEmpty())
	{
		Point now = q.pop();

		for (int i = 0; i < 4; i++)
		{
			Point next(now.r + dR[i], now.c + dC[i]);
			if (!next.isInBoundary(R, C)) continue;

			if ((map[next.r][next.c] == '.' || map[next.r][next.c] == 'S') && dist_water[next.r][next.c] == -1)
			{
				dist_water[next.r][next.c] = dist_water[now.r][now.c] + 1;
				q.push(next);
			}
		}
	}

	// 고슴도치 이동
	dist_goseum[goseum.r][goseum.c] = 0;
	q.push(goseum);

	while (!q.isEmpty())
	{
		Point now = q.pop();

		if (now == target)
		{
			printf("%d\n", dist_goseum[now.r][now.c]);
			return 0;
		}

		for (int i = 0; i < 4; i++)
		{
			Point next(now.r + dR[i], now.c + dC[i]);

			if (!next.isInBoundary(R, C)) continue;
			if (dist_water[next.r][next.c] != -1 && map[next.r][next.c] == '.' && dist_goseum[now.r][now.c] + 1 >= dist_water[next.r][next.c]) continue;

			// 방문X + 빈칸 + 물
			// 방문X + D
			if((map[next.r][next.c] == 'D' && dist_goseum[next.r][next.c] == -1) ||
				(map[next.r][next.c] == '.' && dist_goseum[next.r][next.c] == -1))
			{
				dist_goseum[next.r][next.c] = dist_goseum[now.r][now.c] + 1;
				q.push(next);
			}
		}
	}

	printf("KAKTUS\n");
	return 0;
}