백준/4179/BFS/불!

백준/4179/BFS/불!
BFS 유형중에서 시작지점의 유형이 두 종류일 경우입니다.
처음에는 큐를 두 종류로 나눠서 생각해야되나 했습니다.
그렇게 불을 피하는 진수 큐와 불 큐로 나눠서 BFS를 시도하려했습니다.
구현을 하기전에 로직을 짜기위해 그림을 그려보니 전에 토마토와 같아 한 큐에서 BFS를 시도해보았습니다.

	for(int i=0;i<R;i++)
		for (int j = 0; j < C; j++)
			if (arr[i][j] == 'J') {
				Q.push({ i,j });
				time[i][j] = 1;
			}
	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			if (arr[i][j] == 'F') {
				Q.push({ i,j });
			}
            ...

우선 지훈이가 먼저 움직이고 그 뒤에 불이 퍼져나가게끔 지훈이를 먼저 큐에 넣었습니다.
그리고 지훈이가 이동한 시간을 계산하기 위해 time배열을 사용하였습니다.

	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		if(arr[cur.first][cur.second]=='J'&&(cur.first == 0 || cur.first == R-1 || cur.second == 0 || cur.second == C-1)){
			result = time[cur.first][cur.second];
			break;
		}
		else
			result = 0;
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (arr[cur.first][cur.second] == 'J') {
				if (nx < 0 || nx >= R || ny < 0 || ny >= C)continue;
				if (arr[nx][ny] != '.')continue;
				arr[nx][ny] = 'J';
				time[nx][ny] = time[cur.first][cur.second] + 1;
				Q.push({ nx,ny });
			}
			else if (arr[cur.first][cur.second] == 'F') {
				if (nx < 0 || nx >= R || ny < 0 || ny >= C)continue;
				if (arr[nx][ny] == '#'||arr[nx][ny]=='F')continue;
				arr[nx][ny] = 'F';
				Q.push({ nx,ny });
			}
		}
	}
	if (result == 0) {
		cout << "IMPOSSIBLE" << endl;
	}
	else {
		cout << result << endl;
	}

큐에서 빼낸게 지훈이면 bfs에서 visited 즉, 방문했을 경우를 제외했다면 이번에는 지훈이을 제외한 벽과 불이 있는 곳은 가지 않게 하였습니다. 그리고 방문한 곳은 지훈이가 갈 수 있는 경우의 수를 의미하기 때문에 j라고 표시하였습니다.
다음으로 큐에서 빼넨게 불이라면 불은 지훈이를 덮칠 수 있기 때문에 벽과 불을 제외하고 탐색할 수 있게 하였습니다. 지훈이와 마찬가지로 불 역시 탐색한 곳은 F로 바꿔줬습니다.

if(arr[cur.first][cur.second]=='J'&&(cur.first == 0 || cur.first == R-1 || cur.second == 0 || cur.second == C-1))

마지막으로 해당 조건문을 이용하여 지훈이가 현재 위치에 나갈 공간에 위치할 수 있다면 탈출에 성공한 것이기때문에 while문을 탈출하게 하고 result에 현재 위치에 time 배열 요소를 대입하였습니다.

풀이

1.첫번재 풀이

#include<iostream>
#include<utility>
#include<queue>
#include<string>
using namespace std;
int time[1000][1000];

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

int main(void) {
	string arr[1000];
	ios::sync_with_stdio(0);
	cin.tie(0);

	int R, C,result=1;
	cin >> R >> C;

	for (int i = 0; i < R; i++)
		cin >> arr[i];

	queue<pair<int, int>> Q;

	for(int i=0;i<R;i++)
		for (int j = 0; j < C; j++)
			if (arr[i][j] == 'J') {
				Q.push({ i,j });
				time[i][j] = 1;
			}

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			if (arr[i][j] == 'F') {
				Q.push({ i,j });
			}
	
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		if(arr[cur.first][cur.second]=='J'&&(cur.first == 0 || cur.first == R-1 || cur.second == 0 || cur.second == C-1)){
			result = time[cur.first][cur.second];
			break;
		}
		else
			result = 0;
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (arr[cur.first][cur.second] == 'J') {
				if (nx < 0 || nx >= R || ny < 0 || ny >= C)continue;
				if (arr[nx][ny] != '.')continue;
				arr[nx][ny] = 'J';
				time[nx][ny] = time[cur.first][cur.second] + 1;
				Q.push({ nx,ny });
			}
			else if (arr[cur.first][cur.second] == 'F') {
				if (nx < 0 || nx >= R || ny < 0 || ny >= C)continue;
				if (arr[nx][ny] == '#'||arr[nx][ny]=='F')continue;
				arr[nx][ny] = 'F';
				Q.push({ nx,ny });
			}
		}
	}

	if (result == 0) {
		cout << "IMPOSSIBLE" << endl;
	}
	else {
		cout << result << endl;
	}

}