[BOJ] 3055 : 탈출 (C++)

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

3055번: 탈출

걸린 시간 : 36분 36초

---

BFS를 투트랙으로 하는 문제이다. 비슷한 문제를 풀어본 적이 있는 것 같다..

 

우선, 내 목적은 비버를 D의 위치로 가게 하는 것이다. 여기서 가는 길이 물에 잠겨있다면 이동이 불가능하다는 조건이 붙는다. 이 조건을 위해 물의 흐름의 위치를 (wdist배열) 미리 완성해놓고, 즉 어떤 지점에 물이 몇 초만에 오는지 미리 모두 계산해놓고 비버를 움직인다.

예를 들어, 어떤 지점에 비버가 3초만에 도달할 수 있는데 물도 3초만에 온다고 되어 있으면 바로 continue; 하는 식이다.

 

이 문제를 푸는 법을 잘 떠올리지 못했다면 아마도 물과 비버를 동시에 움직이려고 생각해서 였을것이다. 물의 경로를 미리 모두 생각해놓고 비버를 움직이는 것이 포인트이다.

 

#include <bits/stdc++.h>
using namespace std;

int R, C, goali, goalj;
string board[51];
int wdist[51][51];
int bdist[51][51];
queue<pair<int, int> > wq;
queue<pair<int, int> > bq;
int di[4] = {-1, 0, 0, 1};
int dj[4] = {0, -1, 1, 0};

void input() {
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		cin >> board[i];
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 'S') {
				bq.push({i, j});
				bdist[i][j] = 0;
			}
			else if (board[i][j] == '*') {
				wq.push({i, j});
				wdist[i][j] = 0;
			}
			else if (board[i][j] == 'D') {
				goali = i;
				goalj = j;
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 0; i < 50; i++)
		fill(wdist[i], wdist[i] + 50, -1);
	for (int i = 0; i < 50; i++)
		fill(bdist[i], bdist[i] + 50, -1);
	input();
	while (!wq.empty()) {
		int ci = wq.front().first;
		int cj = wq.front().second;
		wq.pop();
		for (int k = 0; k < 4; k++) {
			int ni = ci + di[k];
			int nj = cj + dj[k];
			if (ni < 0 || ni >= R || nj < 0 || nj >= C || board[ni][nj] == 'X' || board[ni][nj] == 'D' || wdist[ni][nj] != -1)
				continue;
			wq.push({ni, nj});
			wdist[ni][nj] = wdist[ci][cj] + 1;
		}
	}
	while (!bq.empty()) {
		int ci = bq.front().first;
		int cj = bq.front().second;
		bq.pop();
		for (int k = 0; k < 4; k++) {
			int ni = ci + di[k];
			int nj = cj + dj[k];
			if (ni < 0 || ni >= R || nj < 0 || nj >= C || board[ni][nj] == 'X' || bdist[ni][nj] != -1)
				continue;
			if (wdist[ni][nj] != -1 && bdist[ci][cj] + 1 >= wdist[ni][nj])
				continue;
			bq.push({ni, nj});
			bdist[ni][nj] = bdist[ci][cj] + 1;
		}
	}
	if (bdist[goali][goalj] == -1) cout << "KAKTUS";
	else cout << bdist[goali][goalj];
	return 0;
}