백준 3055 - 탈출(복습)

문제 링크입니다. https://www.acmicpc.net/problem/3055

3055번: 탈출

기존의 BFS문제들과는 달리 물이 차오르는 것을 염두해두고 풀어야하는 문제입니다.

따라서 물의 좌표를 저장하는 큐와 고슴도치의 좌표를 저장하는 큐를 만들어야합니다.

고슴도치는 물이 차오를 예정인 곳으로 갈 수 없기 때문에 물을 먼저 차오르게 한다음 고슴도치를 이동했습니다.

물의 좌표에서 상하좌우로 물을 먼저 채운다음 고슴도치를 BFS를 통해 갈 수 있는 곳을 찾은 후, 이차원 배열 check에 몇번 이동했는지 저장했습니다. 

마지막에는 고슴도치의 굴의 위치에 check 배열의 값이 0이 아니라면 1을 빼준후 답을 출력하면 됩니다.

간단한 BFS문제임으로 코드를 보면 이해가 될겁니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

typedef struct qu {
	int x;
	int y;
}qu;
queue<qu> q;
pair<int, int> start, finish;
char miro[51][51];
int arr[4] = { 1,0,-1,0 };
int arr2[4] = { 0,1,0,-1 };
int check[51][51];
bool can_move[51][51];
int R, S;

void bfs() {
	queue<pair<int, int> > water;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= S; j++) {
			if (miro[i][j] == '*') {
				water.push(make_pair(i, j));
			}
		}
	}
	while (!q.empty()) {
		int water_size = water.size();
		for (int i = 0; i < water_size; i++) {
			int x = water.front().first;
			int y = water.front().second;
			water.pop();
			for (int k = 0; k < 4; k++) {
				int water_x = x + arr[k];
				int water_y = y + arr2[k];
				if (water_x >= 1 && water_x <= R && water_y >= 1 && water_y <= S) {
					if (miro[water_x][water_y] == '.') {
						miro[water_x][water_y] = '*';
						water.push(make_pair(water_x, water_y));
					}
				}
			}
		}
		int mole_size = q.size();
		for (int i = 0; i < mole_size; i++) {
			int x = q.front().x;
			int y = q.front().y;
			q.pop();
			for (int k = 0; k < 4; k++) {
				int xx = x + arr[k];
				int yy = y + arr2[k];
				if (xx >= 1 && yy >= 1 && xx <= R && yy <= S) {
					if ((miro[xx][yy] == '.' || miro[xx][yy] == 'D') && check[xx][yy] == 0) {
						check[xx][yy] = check[x][y] + 1;
						q.push({ xx,yy });
					}
				}
			}
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> R >> S;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= S; j++) {
			cin >> miro[i][j];
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= S; j++) {
			if (miro[i][j] == 'S') {
				q.push({ i,j });
				check[i][j] = 1;
			}
			if (miro[i][j] == 'D') {
				finish = make_pair(i, j);
			}
		}
	}
	bfs();
	if (check[finish.first][finish.second] == 0) {
		cout << "KAKTUS";
	}
	else cout << check[finish.first][finish.second] - 1;
	return 0;
}