[백준 BoJ] 3055 - 탈출

// https://www.acmicpc.net/problem/3055
// 탈출
#include<iostream>
#include<queue>
#include<string>

using namespace std;

int R, C;
char map[52][52];
int visited[52][52];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int goalx, goaly;
queue<pair<int, int>> w;
queue<pair<int, int>> q;

int bfs() {
	visited[q.front().first][q.front().second] = 1;
	while (!q.empty()) {

		int wSize = w.size();
		for (int i = 0; i < wSize; i++) {
			int x = w.front().first;
			int y = w.front().second;
			w.pop();

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

				if (nx < 0 || ny < 0 || nx >= R || ny >= C)continue;

				if (map[nx][ny] == '.') {
					map[nx][ny] = '*';
					w.push({ nx,ny });
				}
			}
		}

		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			if (x == goalx && y == goaly) return visited[x][y] - 1;

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

				if (nx < 0 || ny < 0 || nx >= R || ny >= C)continue;

				if (map[nx][ny] != '*' && map[nx][ny] != 'X' && visited[nx][ny] == 0) {
					visited[nx][ny] = visited[x][y] + 1;
					q.push({ nx,ny });
				}
			}
		}

	}
	return -1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < s.size(); j++) {
			map[i][j] = s[j];
			if (s[j] == 'S') {
				q.push({ i,j });
			}
			else if (s[j] == '*') {
				w.push({ i,j });
			}
			else if (s[j] == 'D') {
				goalx = i;
				goaly = j;
			}
		}
	}
	
	int ans = bfs();
	if (ans == -1) cout << "KAKTUS";
	else cout << ans;
}