[BOJ/C++] 4179 불! : BFS

문제

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

풀이

BFS 응용 문제다. 예전에 이와 비슷한 문제를 푼 적이 있는데 지금보니 코드 로직이 비효율적인 것 같아서 더 효율적인 방식으로 풀이했다.

1. 불로 bfs 진행
   (처음에 불의 map을 INF로 초기화하고, 기존 값보다 값이 작으면 갱신하고 큐에 push!)
2. 지훈이 bfs 진행
   (불 map보다 값이 작은 경우에만 계속해서 bfs 진행)

🌟최댓값 초기화할 때, limit.h 헤더 INT_MAX값 이용
🌟큐를 무조건 pair 형태로 할 게 아니라, 구조체 만들어서 구조체 큐 선언하면 코드가 더 깔끔함

코드

#include <iostream>
#include <queue>
#include <limits.h>

using namespace std;

int R, C;
int fire[1001][1001];
char map[1001][1001];
bool visited[1001][1001];
queue<pair<int, int>> fire_q;
int mark = 0;

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

struct moves {
	int x;
	int y;
	int cnt;
};

void f_bfs() {
	while (!fire_q.empty()) {
		int xx = fire_q.front().first;
		int yy = fire_q.front().second;

		fire_q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx < 0 || nx >= R || ny < 0 || ny >= C || map[nx][ny] == '#')	continue;
			if (fire[nx][ny] > fire[xx][yy] + 1) {
				fire[nx][ny] = fire[xx][yy] + 1;
				fire_q.push({ nx, ny });
			}
		}
	}
}

void j_bfs(int x, int y) {
	visited[x][y] = true;

	queue<moves> q;
	q.push({ x, y });
	
	while (!q.empty()) {
		int xx = q.front().x;
		int yy = q.front().y;
		int cnt = q.front().cnt;

		q.pop();

		if (xx == 0 || xx == R - 1 || yy == 0 || yy == C - 1) {
			cout << cnt + 1;
			mark = 1;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx < 0 || nx >= R || ny < 0 || ny >= C || map[nx][ny] == '#' || visited[nx][ny])	continue;
			if (fire[nx][ny] > cnt + 1) {
				visited[nx][ny] = true;
				q.push({ nx, ny, cnt+1 });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int sx = 0, sy = 0;
		
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			fire[i][j] =INT_MAX;
			cin >> map[i][j];
			if (map[i][j] == 'J') {
				sx = i;
				sy = j;
			}
			else if (map[i][j] == 'F') {
				fire_q.push({ i, j });
				fire[i][j] = 0;
			}
		}
	}

	f_bfs();
	j_bfs(sx, sy);

	if(mark == 0)
		cout << "IMPOSSIBLE";

	return 0;
}