[백준 3055] 탈출

문제 출처 : https://www.acmicpc.net/problem/3055

문제 요약

• 맵에 고슴도치(S)와 비버(D)가 있다.
• 고슴도치가 비버에게 가야한다 (S -> D)
• 중간에 돌과 물을 피해서 가야한다. 
• 돌은 고정되어 있고, 물은 고슴도치가 움직이기전에 먼저 찬다.
• 물은 비버와 돌을 제외하고 빈 곳에 물을 점점 채운다.

문제 풀이

문제는 고슴도치가 비버에게 가는 최단거리이다. 앞서 다룬 BFS 의 조건과 같다. 

인접한 노드를 향해 가기 때문에 가중치는 1이다.

따라서, BFS 를 사용하여 답을 찾을 수 있다. 이 문제의 특징은 큐(queue)를 두개를 써야한다는 점이다. 

물에 관한 큐, 고슴도치에 관한 큐 

1. 물을 채운다.

--> 2. 고슴도치가 움직인다.

--->>> 2.1 비버를 만나면 끝

--->>> 2.2 갈 곳이 없다면 종료

--->>> 2.3 갈 곳이 있다면 1번 실행.

위와 같은 알고리즘을 while 문을 사용하여 답을 구한다. 

#include <iostream>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <tuple>

#define MAX 50

using namespace std;

int dx[] = { 0, 0, 1, -1 };

int dy[] = { 1, -1, 0, 0 };

int ans[MAX + 1][MAX + 1];

bool v[MAX + 1][MAX + 1];

int sx(0), sy(0);

int ex(0), ey(0);

int wx(0), wy(0);

int n, m;

queue<pair<int, int>> pour(vector<string> &a, queue<pair<int, int>> water) {

queue<pair<int, int>> ret;

while (!water.empty()) {

int x = water.front().first;

int y = water.front().second;

water.pop();

for (int k = 0; k < 4; k++) {

int nx = x + dx[k];

int ny = y + dy[k];

if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

if (a[nx][ny] == 'X' || (nx == ex && ny == ey) || a[nx][ny] == '*') continue;

if (a[nx][ny] == '.') {

a[nx][ny] = '*';

ret.push(make_pair(nx, ny));

}

}

}

return ret;

}

pair<queue<pair<int, int>>, bool> go(vector<string> &a, queue<pair<int, int>> q) {

queue<pair<int, int>> ret;

bool ok = false;

while (!q.empty()) {

int x = q.front().first;

int y = q.front().second;

q.pop();

for (int k = 0; k < 4; k++) {

int nx = x + dx[k];

int ny = y + dy[k];

if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

if (a[nx][ny] == '*' || a[nx][ny] == 'X' || v[nx][ny] == true) continue;

if (v[nx][ny] == false && (nx == ex && ny == ey)) {

ok = true;

ret.push(make_pair(nx, ny));

v[nx][ny] = true;

ans[nx][ny] = ans[x][y] + 1;

break;

}

if (v[nx][ny] == false && a[nx][ny] == '.') {

ret.push(make_pair(nx, ny));

v[nx][ny] = true;

ans[nx][ny] = ans[x][y] + 1;

}

}

}

return make_pair(ret, ok);

}

int main() {

cin >> n >> m;

vector<string> a(n);

memset(ans, 0, sizeof(ans));

memset(v, false, sizeof(v));

for (int i = 0; i < n; i++) {

cin >> a[i];

}

queue<pair<int, int>> water;

queue<pair<int, int>> q;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (a[i][j] == 'D') {

ex = i; ey = j;

a[i][j] = '.';

}

else if (a[i][j] == 'S') {

sx = i; sy = j;

a[i][j] = '.';

}

else if (a[i][j] == '*') {

wx = i; wy = j;

water.push(make_pair(wx, wy));

}

else

continue;

}

}

q.push(make_pair(sx, sy));

v[sx][sy] = true;

bool fail = false;

bool ok = false;

while (1) {

//물을 먼저 붓는다.

queue<pair<int, int>> nwater = pour(a, water);

queue<pair<int, int>> nq;

//그리고 고슴도치가 움직인다.

tie(nq, ok) = go(a, q);

//만약 더 이상 움직일 곳이 없다면 실패

if (q.empty()) {

fail = true;

break;

}

//움직일 곳이 있고 비버를 만났다면 스톱

else if (!q.empty() && ok) {

break;

}

//이런 경우가 아니라면 새로운 큐를 만들어주기 위해 큐를 복사

else if (!q.empty()) {

water = nwater;

q = nq;

continue;

}

}

if (fail) {

cout << "KAKTUS" << endl;

}

else {

cout << ans[ex][ey] << endl;

}

return 0;

}