백준 4179 C++

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

4179번: 불!

이거 생각보다 어려웠습니다...

처음에 조금이라도 메모리를 절약해보겠다고 visited를 사용하지 않고 if문을 엄청 꼬아서 하니까

어디서 반례가 나타나는지 모르겠어서 그냥 visited를 만들어서 했습니다.

최단 거리니까 BFS를 사용했고 다양한 반례에 대해서는 한번 직접 생각하시면서 해보시는게 나을거 같습니다.

#include <iostream>
#include <queue>

using namespace std;

int INF = 987654321;
int n, m;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
char A[1010][1010];
queue<pair<int, int>> Fq;
queue<pair<int, int>> Jq;
int FireMove[1010][1010];
int JiMove[1010][1010];
int visited[1010][1010];
int Jvisited[1010][1010];
int escape = -1;

void FireBfs()
{
	while (!Fq.empty()) {
		int a = Fq.front().first;
		int b = Fq.front().second;
		Fq.pop();

		int temp = FireMove[a][b];
		visited[a][b] = 1;

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

			if (ny < 0 || nx < 0 || ny > n + 1 || nx > m + 1) continue;

			if (!visited[ny][nx] && A[ny][nx] == '.') {		//불이 [ny][nx]에 방문하지 않았거나 이제 [ny][nx]에 들어갈 값이 원래 있던 값보다 작다면 (지금 불이 먼저 온거라면) 
				visited[ny][nx] = 1;
				FireMove[ny][nx] = temp + 1;
				Fq.push({ ny, nx });		// '.'인 경우면 queue에 푸쉬해서 다음 불이 번지도록 한다. -> E라는 이유 때문에 넣음.
			}
		}
	}
}

void JBfs() {
	while (!Jq.empty()) {
		int a = Jq.front().first;
		int b = Jq.front().second;
		int temp = JiMove[a][b];
		Jq.pop();

		if (JiMove[a][b] == FireMove[a][b]) continue;

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

			if (ny < 0 || nx < 0 || ny > n + 1 || nx > m + 1) continue;

			if (!Jvisited[ny][nx] && FireMove[ny][nx] > temp + 1) {		//[ny][nx]는 방문한 적이 없고 [ny][nx]칸에 넣을 값이 Fire[ny][nx]보다 작다면 -> 불보다 지훈이가 먼저 왔다면 같으면 안됌.
				Jvisited[ny][nx] = 1;
				if (A[ny][nx] == '.') {
					JiMove[ny][nx] = temp + 1;
					Jq.push({ ny, nx });
				}
				else if (A[ny][nx] == 'E' ) {
					escape = temp + 1;
					JiMove[ny][nx] = temp + 1;
					return;
				}
			}


		}
	}
}

int main()
{
	cin >> n >> m;

	fill(&A[0][0], &A[0][0] + 1010 * 1010, 'E');
	fill(&FireMove[0][0], &FireMove[0][0] + 1010 * 1010, INF);
	fill(&JiMove[0][0], &JiMove[0][0] + 1010 * 1010, INF);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char c; cin >> c;
			A[i][j] = c;
			if (c == 'J') {
				Jq.push({ i,j });
				JiMove[i][j] = 0;
			}
			if (c == 'F') {
				Fq.push({ i, j });
				FireMove[i][j] = 0;
			}
		}
	}

	FireBfs();
	JBfs();

	////Fire
	//cout << "Fire\n";
	//for (int i = 0; i <= n+1; i++) {
	//	for (int j = 0; j <= m+1; j++) {
	//		cout << FireMove[i][j] << " ";
	//	}
	//	cout << "\n";
	//}

	//////Jihoon
	//cout << "Jihoon\n";
	//for (int i = 0; i <= n + 1; i++) {
	//	for (int j = 0; j <= m + 1; j++) {
	//		cout << JiMove[i][j] << " ";
	//	}
	//	cout << "\n";
	//}

	if (escape == -1) {
		cout << "IMPOSSIBLE";
	}
	else {
		cout << escape;
	}


}

 

근데 너무 억울해서 visited 없는 버전도 완성하긴 했습니다.

#include <iostream>
#include <queue>

using namespace std;

int n, m;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
char A[1010][1010];
queue<pair<int, int>> Fq;
queue<pair<int, int>> Jq;
int FireMove[1010][1010];
int JiMove[1010][1010];
int escape = -1;

void FireBfs()
{
	while (!Fq.empty()) {
		int a = Fq.front().first;
		int b = Fq.front().second;
		Fq.pop();

		int temp = FireMove[a][b];

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

			if (ny < 0 || nx < 0 || ny > n + 1 || nx > m + 1) continue;

			if (FireMove[ny][nx] == -1 &&  A[ny][nx] == '.') {		//불이 [ny][nx]에 방문하지 않았거나 이제 [ny][nx]에 들어갈 값이 원래 있던 값보다 작다면 (지금 불이 먼저 온거라면)
				FireMove[ny][nx] = temp + 1;
				Fq.push({ ny, nx });		// '.'인 경우면 queue에 푸쉬해서 다음 불이 번지도록 한다. -> E라는 이유 때문에 넣음.
			}
		}
	}
}

void JBfs() {
	while (!Jq.empty()) {
		int a = Jq.front().first;
		int b = Jq.front().second;
		int temp = JiMove[a][b];
		Jq.pop();

		if (JiMove[a][b] == FireMove[a][b]) continue;

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

			if (ny < 0 || nx < 0 || ny > n + 1 || nx > m + 1) continue;

			if (JiMove[ny][nx] == -1 && (FireMove[ny][nx] > temp + 1 || FireMove[ny][nx] == -1)) {		//[ny][nx]는 방문한 적이 없고 [ny][nx]칸에 넣을 값이 Fire[ny][nx]보다 작다면 -> 불보다 지훈이가 먼저 왔다면 같으면 안됌.
				if (A[ny][nx] == '.') {
					JiMove[ny][nx] = temp + 1;
					Jq.push({ ny, nx });
				}
				else if (A[ny][nx] == 'E') {
					escape = temp + 1;
					JiMove[ny][nx] = temp + 1;
					return;
				}
			}


		}
	}
}

int main()
{
	cin >> n >> m;

	fill(&A[0][0], &A[0][0] + 1010 * 1010, 'E');
	fill(&FireMove[0][0], &FireMove[0][0] + 1010 * 1010, -1);
	fill(&JiMove[0][0], &JiMove[0][0] + 1010 * 1010, -1);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char c; cin >> c;
			A[i][j] = c;
			if (c == 'J') {
				Jq.push({ i,j });
				JiMove[i][j] = 0;
			}
			if (c == 'F') {
				Fq.push({ i, j });
				FireMove[i][j] = 0;
			}
		}
	}

	FireBfs();
	JBfs();

	////Fire
	//cout << "Fire\n";
	//for (int i = 0; i <= n+1; i++) {
	//	for (int j = 0; j <= m+1; j++) {
	//		cout << FireMove[i][j] << " ";
	//	}
	//	cout << "\n";
	//}

	////Jihoon
	//cout << "Jihoon\n";
	//for (int i = 0; i <= n + 1; i++) {
	//	for (int j = 0; j <= m + 1; j++) {
	//		cout << JiMove[i][j] << " ";
	//	}
	//	cout << "\n";
	//}

	if (escape == -1) {
		cout << "IMPOSSIBLE";
	}
	else {
		cout << escape;
	}


}