[BOJ/BFS] BOJ 4179 - 불! 문제(C++)

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

4179번: 불!

 

문제풀이

지훈이가 탈출할 수 있는 가장 빠른시간을 구해야한다 문제를 보자마자 bfs로 접근이 필요한 것을 확신할 수 있다 단 4방향으로 퍼지는 불을 생각해야 한다 4방향으로 퍼지는 불 + 불은 여러개가 있을 수 있음에서 결국 문제를 해결하지 못했다.

 

첫번쨰로 지훈이가 불을 피해서 도망갈 수 있는경우와 그렇지 못한 경우를 생각해야 한다 불이 퍼지는 최단거리와 지훈이가 탈출하는 최단거리 테이블을 비교하여 지훈이의 위치가 불의 위치보다 빠르다면 지훈이는 해당 위치로 도망갈 수 있다.

지훈이의 시작위치 -> 0, 0

불의 시작위치 -> 0, 1

0(J) 1(F)	0(F) 1(J)
1(J) 2(F) -> 이동가능	2(J) 1(F) -> 이동불가(이미 불이번짐)
2(J) 3(F) -> 이동가능	3(J) 2(F) -> 이동불가

 

표처럼 만약 지훈이가 이동하려는 위치가 이미 불이 번진상태임을 bfs에서 이동하기 전에 체크해주면 된다.

void find_exit(queue<pair<int, int>> q){
	while(q.size()){
		tie(y, x) = q.front(); q.pop();
		if(y == 0 || x == 0 || y == r - 1 || x == c - 1){
			ret = person[y][x];
			break;
		}
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
			if(person[ny][nx]) continue;
			if(a[ny][nx] == '#') continue;
			if(person[y][x] + 1 >= fire[ny][nx]) continue;
			person[ny][nx] = person[y][x] + 1;
			q.push({ny, nx});
		}

	}
	return;
}

person[y][x] + 1 이동하려는 위치의 값이 불의 최단거리와 같거나 크다면 이동을 하지 않도록 처리해준다. 만약 이동이 가능하다면 최단거리를 갱신해주면 된다.

 

정답코드

#include <bits/stdc++.h>
using namespace std;
const int INF = 99999999;
int r, c, sy, sx, person[1001][1001], fire[1001][1001], ret, y, x;
char a[1001][1001];
int dy[] = {-1, 0, 1, 0}; int dx[] = {0, 1, 0, -1};

void spread_fire(queue<pair<int, int>> q){
	while(q.size()){
		tie(y, x) = q.front(); q.pop();
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
			if(fire[ny][nx] != INF || a[ny][nx] == '#') continue;
			fire[ny][nx] = fire[y][x] + 1;
			q.push({ny, nx});
		}
	}
	return;
}

void find_exit(queue<pair<int, int>> q){
	while(q.size()){
		tie(y, x) = q.front(); q.pop();
		if(y == 0 || x == 0 || y == r - 1 || x == c - 1){
			ret = person[y][x];
			break;
		}
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || nx < 0 || ny >= r || nx >= c) continue;
			if(person[ny][nx]) continue;
			if(a[ny][nx] == '#') continue;
			if(person[y][x] + 1 >= fire[ny][nx]) continue;
			person[ny][nx] = person[y][x] + 1;
			q.push({ny, nx});
		}

	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> r >> c;
	queue<pair<int, int>> q;
	fill(&fire[0][0], &fire[0][0] + 1001 * 1001, INF);
	for(int i = 0; i < r; i++){
		for(int j = 0; j < c; j++){
			cin >> a[i][j];
			if(a[i][j] == 'J'){sy = i; sx = j;}
			if(a[i][j] == 'F'){
				fire[i][j] = 1;
				q.push({i, j});
			}
		}
	}
	spread_fire(q);
	person[sy][sx] = 1;
	queue<pair<int, int>> q2;
	q2.push({sy, sx});
	find_exit(q2);
	if(ret != 0) cout << ret << '\n';
	else cout << "IMPOSSIBLE" << '\n';
    return 0;
}

조금 귀찮더라도 코드가 길어져서 헷갈리기 때문에 일부러 2개의 함수를 만들어서 처리했다

아직은 골드 문제는 정답이나 힌트를 안보고 풀기는 어렵다 하지만 풀면서 경험치가 쌓이는 기분이다.