[백준] 3055번 탈출

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

3055번: 탈출

가중치가 없는 최단경로를 구하는 것이기 때문에 BFS로 풀었다. 한 가지 주의할 점은 큐에서 빼낼 때 한 번에 하나씩 빼내는 것이 아니라 같은 시점에 큐에 넣어진 것들은 한번에 큐에서 빼주는 것이다. 그래야 물이 차는 속도와 맞출 수 있다. 나는 원래 절대 구글링을 하거나 힌트도 보지 않고 풀지만 이 문제는 조금 어려운 것 같아서 푸는 방법을 혼자 생각해 낸 것이 특히 더 뿌듯했다. 물이 차는 것은 딱히 BFS나 DFS로 풀지 않고 그냥 매 시점 물이 찬 곳과 인접한 동서남북을 물로 채워주었다. 다음에 찰 예정인 곳은 콤마(,)로 표시해놓고 고슴도치가 이동한 후에 별(*)로 표시해주었다.

4ms로 통과했다.

#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>
#include <queue>
using namespace std;

int dr[] = { 0, 0, -1, 1 };
int dc[] = { 1, -1, 0, 0 };

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	pair<int, int> waterLocation;
	pair<int, int> sLocation;
	vector<vector<char>> v(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> v[i][j];
			if (v[i][j] == '*')
				waterLocation = make_pair(i, j);
			if (v[i][j] == 'S')
				sLocation = make_pair(i, j);
		}
	}

	int minLength = -1;
	queue<tuple<int, int, int, int>> q;
	q.push(make_tuple(sLocation.first, sLocation.second, 0, 0));
	vector<vector<bool>> visited(n, vector<bool>(m, false));

	int cnt = 1;
	bool arrivedFlag = false;
	while (!q.empty()) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (v[i][j] == '*') {
					for (int k = 0; k < 4; k++) {
						int row = i + dr[k];
						int col = j + dc[k];
						if (row >= n || col >= m || row < 0 || col < 0 || v[row][col] != '.')
							continue;
						v[row][col] = ',';
					}
				}
			}
		}
		while (!q.empty()) {
			tuple<int, int, int, int> cur = q.front();
			if (get<3>(cur) != cnt - 1)
				break;
			q.pop();
			if (v[get<0>(cur)][get<1>(cur)] == 'D') {
				minLength = get<2>(cur);
				break;
			}
			if (!visited[get<0>(cur)][get<1>(cur)]) {
				visited[get<0>(cur)][get<1>(cur)] = true;
				for (int i = 0; i < 4; i++) {
					int row = get<0>(cur) + dr[i];
					int col = get<1>(cur) + dc[i];
					if (row >= n || col >= m || row < 0 || col < 0 || !(v[row][col] == '.' || v[row][col] == 'D'))
						continue;
					if (v[row][col] == 'D') {
						arrivedFlag = true;
						minLength = get<2>(cur) + 1;
						break;
					}
					q.push(make_tuple(row, col, get<2>(cur) + 1, cnt));
				}
			}
			if (arrivedFlag)
				break;
		}
		if (arrivedFlag)
			break;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (v[i][j] == ',') {
					v[i][j] = '*';
				}
			}
		}
		cnt++;
	}
	if (minLength == -1)
		cout << "KAKTUS";
	else
		cout << minLength;
	return 0;
}