[백준] 4179번 불!

링크

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

4179번: 불!

풀이

 

지훈이가 불이 도달하기 전에 미로를 탈출할 수 있는지 없는지를 구하는 문제이다.

 

최단경로를 찾는거기 때문에 먼저 BFS를 이용하여 문제를 접근했다.

 

문제를 어떻게 풀까 생각하다 지훈이와 불에 대한 2차원 배열을 각각 따로 만들어

 

 

지훈이의 배열에는 불을 제외하고 벽과 빈공간 지훈이만을 놓고 지훈이가 갈 수 있는 길을 BFS탐색으로 돌리고

 

불 또한 지훈이를 빼놓고 BFS 탐색을 돌렸다.

 

백준에 있는 예시를 예로 들어보면

 

 

 

 

 

위의 설명대로 지훈이와 불만 따로 BFS 탐색을 돌리게 되면

 

그리고 위의 2개를 하나로 합쳐 보면

 

탈출할수 있는 벽의 경계선을 마주한 위치에서

 

지훈이가 불보다 빨리 도착하는 곳이 있다면

그곳은 지훈이가 탈출할 수 있는 곳이 된다.

 

이 방법을 이용하여 문제를 풀었습니다.

 

 

 

 

 

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 20000000;

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

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

char board[SIZE][SIZE];

//0은 man    1은 fire
int cnt[SIZE][SIZE][2];
bool visited[SIZE][SIZE][2];

queue<pair<int, pair<int, int>>> q;

bool is_escape(int N, int M) {
	int res = INF;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
				if (cnt[i][j][0] < cnt[i][j][1]) {
					res = min(res, cnt[i][j][0] + 1);
				}
			}
		}
	}

	if (res != INF) {
		cout << res;
		return true;
	}
	return false;
}

void init(int N, int M) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cnt[i][j][0] = cnt[i][j][1] = INF;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	
	int N, M; cin >> N >> M;

	init(N,M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];

			if (board[i][j] == 'J') {
				q.push({ i,{j,0} });
				cnt[i][j][0] = 0;
			}
			else if (board[i][j] == 'F') {
				q.push({ i,{j,1} });
				cnt[i][j][1] = 0;
			}
		}
	}

	while (!q.empty()) {
		pair<int, pii> h = q.front(); q.pop();
		
		visited[h.first][h.second.first][h.second.second] = true;
	
		for (int d = 0; d < 4; d++) {
			pair<int, pii> n;
			n.first = h.first + dx[d];
			n.second.first = h.second.first + dy[d];
			n.second.second = h.second.second;

			if (n.first < 0 || n.first >= N || n.second.first < 0 || n.second.first >= M)
				continue;

			if (visited[n.first][n.second.first][n.second.second] == true)
				continue;

			if (board[n.first][n.second.first] == '#')
				continue;
			cnt[n.first][n.second.first][n.second.second] = cnt[h.first][h.second.first][h.second.second] + 1;
			visited[n.first][n.second.first][n.second.second] = true;

			q.push(n);
		}
	}

	if (is_escape(N, M)) {
		return 0;
	}
	else {
		cout << "IMPOSSIBLE";
	}

	return 0;


}