[백준] 4179-불!(C++)

문제링크:https://www.acmicpc.net/problem/4179

4179번: 불!

 

5427번 불의 이전단계 문제입니다.

 

알고리즘은

• 1. 불먼저 전파
• 2. 사람 이동
• 1, 2번을 사람이 이동가능한 칸이 있을 때 까지 반복
• 3. 결과 값 도출

순입니다.

 

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int h = 0, w = 0;
int visited[1000][1000] = { 0 };
char arr[1000][1000];

queue <int> fire[2];
queue <int> people[2];

int x_ar[4] = { -1,1,0,0 };
int y_ar[4] = { 0,0,1,-1 };

void bfs() {
	//초기값 입력
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			if (arr[i][j] == 'F')
				fire[0].push(i), fire[1].push(j);
			else if (arr[i][j] == 'J')
				people[0].push(i), people[1].push(j), visited[i][j] = 1;



	while (!people[0].empty()) { //상근이가 이동할 경로가 없을 때 까지 반복
								 //1. 불먼저 전파
		int fire_cnt = fire[0].size();
		while (fire_cnt--) {
			int yy = fire[0].front();
			int xx = fire[1].front();
			fire[0].pop(), fire[1].pop();
			for (int i = 0; i < 4; i++) {
				int y = yy + y_ar[i];
				int x = xx + x_ar[i];
				if (y >= 0 && y < h && x >= 0 && x < w)
					if (arr[y][x] == '.' || arr[y][x] == 'J') {
						arr[y][x] = 'F';
						fire[0].push(y), fire[1].push(x);
					}
			}
		}
		//2. 상근좌 이동
		int people_cnt = people[0].size();
		while (people_cnt--) {
			int yy = people[0].front();
			int xx = people[1].front();
			people[0].pop(), people[1].pop();
			for (int i = 0; i < 4; i++) {
				int y = yy + y_ar[i];
				int x = xx + x_ar[i];
				if (y >= 0 && y < h && x >= 0 && x < w)
					if (arr[y][x] == '.' && visited[y][x] == 0) {
						visited[y][x] = visited[yy][xx] + 1;
						people[0].push(y), people[1].push(x);
					}
			}
		}
	}
	//3. 모서리의 visited값들을 확인하고 결과값을 도출
	int result = 1000000;
	bool alive = false;
	for (int i = 0; i < h; i++) {
		if (visited[i][0] != 0) {
			alive = true;
			if (visited[i][0] < result)
				result = visited[i][0];
		}
		if (visited[i][w - 1] != 0) {
			alive = true;
			if (visited[i][w - 1] < result)
				result = visited[i][w - 1];
		}
	}
	for (int j = 0; j < w; j++) {
		if (visited[0][j] != 0) {
			alive = true;
			if (visited[0][j] < result)
				result = visited[0][j];
		}
		if (visited[h - 1][j] != 0) {
			alive = true;
			if (visited[h - 1][j] < result)
				result = visited[h - 1][j];
		}
	}

	if (alive)
		cout << result << '\n';
	else
		cout << "IMPOSSIBLE" << '\n';
}

int main() {

	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		string val;
		cin >> val;
		for (int j = 0; j < val.size(); j++)
			arr[i][j] = val[j];
	}
	bfs();

}

비슷한 유형문제를 풀어보셨다면 어렵지 않습니다.

꼭 이 문제 직접구현해보시고 bfs에 익숙해지세요! 화이팅