[백준] 백준 4179번 불!

백준 4179번 문제소개

먼저 BFS를 사용하여 풀 수 있는 문제 이다.

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

4179번: 불!

백준 4179번 문제풀이

Input : 

4 4

####

#JF#

#. .#

#. .#

 

Output:

3

 

이 문제같은 경우에는  일반적인 탈출문제와 거의 똑같다.

 

조건을 말해보자

 

> J(지훈)

1.벽으로 이동을 못한다.

2.지훈이 탈출하지 못하면 IMPOSSIBLE 출력

3. 4방향으로 갈수있다. (변수 dir 사용)

4. 길을 변경하지않고 최적의 길을 찾음

 

> F(불)

1. 지훈과 동시에 이동한다.

2. 벽으로 이동을 못한다.

3. 4방향으로 갈수있다. (변수 dir 사용)

4. 4방향 전부 간 곳을 길에서 불로 변경

 

위의 조건 대로 코드를 작성하여 불은 길에만 붙을 수 있다. 지훈또한 길만 갈 수 있다. 지훈이 간 장소는 visited배열에 저장하고, 불이 간 장소는 그 위치에 불을 넣어주는 거다 그럼 F는 길이 아니기 때문에 지훈이가 고립되는 경우가 생긴다. 바로 그 때가 탈출하지 못했을 때고, F가 길을 막지않고 제일 끝쪽 index에 도착하면 둘 다 이동이 끝났을 때 증가 시킨 result를 반환시켜준다. 이때 result 같은 경우에는 몇번 움직였는가와도 같은 것이다. 이 때 이동이 끝났을 때의 조건문에 들어가지않고 while문을 빠져나와서 return -1로 반환되게 되면 고립되어서 탈출할수 없는 상태이므로, IMPOSSIBLE이라고 출력한다.

 

 

<소스코드>

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
// # : Solid, .:Road
char map[1001][1001];
int visited[1001][1001];
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

int r, c;
queue<pair<int, int>> Fire;
pair<int, int> start;

int BFS() {
	queue<pair<int, int>> jj;
	int result = 0;
	jj.push(make_pair(start.first, start.second));
	visited[start.first][start.second] = 1;
	while (!jj.empty()) {
		int Fsize = Fire.size();
		for (int i = 0; i < Fsize; i++) {
			int x = Fire.front().first;
			int y = Fire.front().second;
			Fire.pop();
			for (int j = 0; j < 4; j++) {
				int n_x = x + dir[j][0];
				int n_y = y + dir[j][1];
				if ((0 <= n_x && n_x < r)&& (0 <= n_y && n_y < c)) {
					if (visited[n_x][n_y] ==0 &&map[n_x][n_y] =='.') {
						Fire.push(make_pair(n_x, n_y));
						map[n_x][n_y] = 'F';
						
					}
				}
			}
		}
		int Jsize = jj.size();
		for (int i = 0; i < Jsize; i++) {
			int x = jj.front().first;
			int y = jj.front().second;
			jj.pop();
			if (x==0||r-1 == x || c-1 == y||y==0) {
				return result+1;
			}
			for (int j = 0; j < 4; j++) {
					int n_x = x + dir[j][0];
					int n_y = y + dir[j][1];	
					if (visited[n_x][n_y] == 0 && map[n_x][n_y] != '#' && map[n_x][n_y] != 'F') {
						jj.push(make_pair(n_x, n_y));
						visited[n_x][n_y] = visited[x][y] + 1;
					}
					
			}
		}
		result++;
	}
	return -1;
}
void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
int main() {
	init();
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin>>map[i][j];
			if (map[i][j] == 'J') {
				start = make_pair(i, j);
			}
			else if (map[i][j] == 'F') {
				Fire.push(make_pair(i, j));
			}
		}
	}
	int temp = BFS();
	if (temp == -1) {
		cout << "IMPOSSIBLE";
	}
	else {
		cout << temp;
	}
}

 

피드백이 있으면 댓글 남겨주세요~~