[백준 ]5427 불

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

 

BFS문제입니다

불이 번지는 상황과 상근이가 탈출하는 상황을 각각 BFS를 사용해주고,

특정 칸에 불이 번지는 최소 시간 t1이라고 하고

상근이가 틍정 칸으로 이동하는 최소시간을 t2라 할때

t1>t2+1이여야 이동할 수 있습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, INF = 987654321;

using namespace std;

int TC, N, M, v[1001][1001], v2[1001][1001];
char mp[1001][1001];
int main() {
	FAST;
	cin >> TC;
	while (TC--) {
		cin >> M >> N;
		queue<pi>fq;
		queue<pi>eq;
		vector<pi>out;
		mset(mp);
		mset(v);
		mset(v2);
		REP(i, N)REP(j, M) {
			cin >> mp[i][j];
			if (mp[i][j] == '@') {
				v2[i][j] = 1;
				eq.push({ i,j });
			}
			if (mp[i][j] == '*') {
				v[i][j] = 1;
				fq.push({ i,j });
			}
			if ((i == 1 || i == N || j == 1 || j == M) && mp[i][j] != '#') {
				out.push_back({ i,j });
			}
		}

		while (!fq.empty()) {
			auto [y, x] = fq.front();
			fq.pop();
			rep(i, 4) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny >= 1 && ny <= N && nx >= 1 && nx <= M && mp[ny][nx] != '#' && !v[ny][nx]) {
					v[ny][nx] = v[y][x] + 1;
					fq.push({ ny,nx });
				}
			}
		}
		while (!eq.empty()) {
			auto [y, x] = eq.front();
			eq.pop();
			rep(i, 4) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny >= 1 && ny <= N && nx >= 1 && nx <= M && mp[ny][nx] != '#' && (!v[ny][nx] || v[ny][nx]>v2[y][x]+1) && !v2[ny][nx]) {
					v2[ny][nx] = v2[y][x] + 1;
					eq.push({ ny,nx });
				}
			}
		}
		int ans = INT_MAX;
		for (auto [y, x] : out) {
			if (v2[y][x]) {
				ans = min(ans, v2[y][x]);
			}
			
		}
		ans == INT_MAX ? cout << "IMPOSSIBLE\n" : cout << ans << "\n";
	}
}