[백준] 5427-불(C++)

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

5427번: 불

 

 bfs문제입니다.

불과 상근이가 함께 이동하기 때문에 각각 bfs를 사용해서 구현하시면 되는 문제입니다.

 

 

문제조건에서 

상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

이라고 하기 때문에 불을 먼저 움직여주면 됩니다.

 

알고리즘은

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

순입니다.

 

 

 

 

 

 

정답코드입니다.

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int t = 0, 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] == '*')
				fire[0].push(i), fire[1].push(j);
			else if(arr[i][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] == '@') {
						arr[y][x] = '*';
						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 >> t;

	while (t--) {
		memset(visited, 0, sizeof(visited));
		while (!fire[0].empty())
			fire[0].pop(), fire[1].pop();

		cin >> w >> h;
		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에 익숙해지세요! 화이팅