백준 3055번 : 탈출 (c++)

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

3055번: 탈출

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면고슴도치가 물에 빠지기 때문이다.

입력

|첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.
다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

예제 입력
3 3
D.*
...
.S.
예제 출력 
3
예제 입력 
3 3
D.*
...
..S
예제 출력 
KAKTUS

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

struct Point {
	int y;
	int x;
	char type;
};

int R, C;
char map[50][50];
int dp[50][50];
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
queue <Point> q;
vector <Point> wlist;

bool chkSafe(int y, int x) {
	if (map[y][x] == 'D') {
		return true;
	}
	else if (map[y][x] == '.') {
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && map[ny][nx] == '*') {
				return false;
			}
		}
		return true;
	}
	else {
		return false;
	}
}

int main() {
	
	freopen("input.txt", "r", stdin);
	cin >> R >> C;
	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 'S') {
				q.push({ i,j,'S' });
			}
			else if (map[i][j] == '*') {
				wlist.push_back({ i,j,'*' });
			}
		}
	}
	
	q.push({ wlist[0].y,wlist[0].x,wlist[0].type });
	
	bool foundAnswer = false;

	while (!q.empty()) {
		Point p = q.front();
		q.pop();
		if (p.type == 'D') {
			cout << dp[p.y][p.x];
			foundAnswer = true;
			break;
		}
		for (int i = 0; i < 4; i++)
		{
			int ny = p.y + dy[i];
			int nx = p.x + dx[i];
			if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
			if (p.type == '.' || p.type == 'S') {
				//고슴도치 이동
				if (dp[ny][nx] == 0 && chkSafe(ny, nx)) {
					dp[ny][nx] = dp[p.y][p.x] + 1;
					q.push({ ny,nx,map[ny][nx] });
				}
			}
			else if (p.type == '*' && map[ny][nx] == '.') {
				//물이동
				q.push({ ny,nx,'*' });
				map[ny][nx] = '*';
			}
		}
	}
	if (!foundAnswer) {
		cout << "KAKTUS";
	}
	return 0;
}