C++ / 백준 / 3055 / 탈출

문제

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

3055번: 탈출

 

문제풀이

5427번 불과 유사한 문제이다.

물이 먼저 차오른 뒤 고슴도치가 움직인다.

고슴도치의 위치를 나타내는 loc큐, 물의 위치를 나타내는 water큐를 선언한다.

각 큐는 벡터로 구성되고 y좌표, x좌표, 몇 분이 지났는지를 나타낸다.

pre와 cnt, w_pre, w_cnt는 1분이 지났을 때 더 이상 while문이 돌지 않도록 하기 위해 분을 나타내는 변수이다.

while(1) 문을 실행하고 water큐가 비거나 w_pre가 w_cnt와 같지 않을 때(1분이 지날 때)까지 while문을 돌리면서 물이 차오를 수 있는 위치를 확인하고 물을 채운다. 그 뒤 y좌표, x좌표, 분을 큐에 집어넣는다.

1분이 지나 물이 모두 차오르면 while문을 통해 고슴도치를 움직인다.

1분 동안(한 칸) 모두 움직일 수 있는 위치를 확인하고 loc큐에 y좌표, x좌표, 분을 집어넣는다.

만약 다음칸이 D라면 분+1을 출력하고 종료한다.

고슴도치가 더 이상 이동할 수 없으면 KAKTUS를 출력하고 종료한다.

 

 

 

코드

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

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int R(0), C(0);
	cin >> R >> C;
	int y(0), x(0);
	vector<vector<char>>map(R, vector<char>(C, ' '));
	vector<vector<bool>>visit(R, vector<bool>(C, false));
	queue<vector<int>>water;
	queue<vector<int>>loc;

	for (y = 0; y < R; ++y) {
		for (x = 0; x < C; ++x) {
			cin >> map[y][x];
			if (map[y][x] == '*')
				water.push({ y,x,0 });
			else if (map[y][x] == 'S') {
				loc.push({ y,x,0 });
				visit[y][x] = true;
			}
		}
	}
	int pre(0), cnt(0);
	int w_pre(0), w_cnt(0);
	int idx(0);
	while (1) {
		while (!water.empty()) {
			y = water.front()[0];
			x = water.front()[1];
			w_cnt = water.front()[2];

			if (w_pre != w_cnt)
				break;
			
			else water.pop();
			for (idx = 0; idx < 4; ++idx) {
				int n_y(y + dy[idx]);
				int n_x(x + dx[idx]);
				if (n_y >= 0 && n_y < R && n_x >= 0 && n_x < C) {
					if (map[n_y][n_x] == '.' && !visit[n_y][n_x]) {
						map[n_y][n_x] = '*';
						water.push({ n_y,n_x,w_cnt + 1 });
					}
				}
			}			
		}
		w_pre = w_cnt;

		while (!loc.empty()) {
			y = loc.front()[0];
			x = loc.front()[1];
			cnt = loc.front()[2];
			if (pre != cnt)
				break;			
			else loc.pop();
			for (idx = 0; idx < 4; ++idx) {
				int n_y(y + dy[idx]);
				int n_x(x + dx[idx]);
				if (n_y >= 0 && n_y < R && n_x >= 0 && n_x < C) {
					if (map[n_y][n_x] == '.' && !visit[n_y][n_x]) {
						visit[n_y][n_x] = true;
						loc.push({ n_y,n_x,cnt + 1 });
					}
					else if (map[n_y][n_x] == 'D') {
						cout << cnt + 1;
						exit(0);
					}
				}
			}
		}
		pre = cnt;
		if (loc.empty()) break;
	}
	cout << "KAKTUS";
}