[백준] 4179 불!

[백준] 4179 불!

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

틀린 풀이

• 7%에서 메모리 초과

• 보드의 크기 최대 1000 $*$ 1000
  -> 보드 전체에 불이 확산된 경우, 보드 내 모든 불의 좌표를 저장하는 벡터(fire)의 크기 1000 $*$ 1000
  -> 메모리 초과

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int R, C;
vector<string> board;

int dirR[4] = { 0, 1, -1, 0 };
int dirC[4] = { -1, 0, 0, 1 };

bool outOfBoard(int r, int c) {
	if (r < 0 || r >= R) return true;
	if (c < 0 || c >= C) return true;
	return false;
}


//보드 불의 좌표
vector<pair<int, int>> fire;

//보드 불 확산
void boardFire() {
	
	//새로 확산된 불의 좌표
	vector<pair<int, int>> newFire;

	vector<vector<int>> visited(R, vector<int>(C, 0));

	for(int i = 0; i<fire.size(); ++i){
		int curR = fire[i].first;
		int curC = fire[i].second;
		visited[curR][curC] = 1;

		for (int d = 0; d < 4; ++d) {
			int nextR = curR + dirR[d]; 
			int nextC = curC + dirC[d];

			if (outOfBoard(nextR,nextC)) continue;
			if (board[nextR][nextC] == '#') continue;
			if (visited[nextR][nextC]) continue;
			
			board[nextR][nextC] = 'F';
			newFire.push_back({ nextR, nextC });
		}
	}

	for (int i = 0; i < newFire.size(); ++i) {
		fire.push_back(newFire[i]);
	}

	return;
}

int solve(int startR, int startC) {

	vector<vector<int>> visited(R, vector<int>(C, 0));
	//<-time, 현재 좌표 pair>
	priority_queue<pair<int, pair<int,int>>> q;
	q.push({ 0, {startR, startC} });

	int boardTime = 0;
	while (!q.empty()) {
		int curTime = -q.top().first;
		int curR = q.top().second.first;
		int curC = q.top().second.second;
		q.pop();

		if (visited[curR][curC]) continue;
		visited[curR][curC] = 1;

		while(boardTime < curTime) {
			boardFire();
			boardTime++;
		}
		//현재 위치에 불이 번졌는지 확인!!
		if (board[curR][curC] == 'F') continue;

		for (int d = 0; d < 4; ++d) {
			int nextR = curR + dirR[d];
			int nextC = curC + dirC[d];

			//다음 이동시 보드 밖인 경우 탈출 성공
			if (outOfBoard(nextR, nextC)) {
				return curTime + 1;
			}

			//다음 칸으로 이동
			if (board[nextR][nextC] == '#') continue;
			if (board[nextR][nextC] == 'F') continue;
			if (visited[nextR][nextC]) continue;
			q.push({ -(curTime + 1),{nextR, nextC} });
		}
	}

	//탈출 불가능
	return -1;
}

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

	cin >> R >> C;

	pair<int, int> start = { -1, -1 };

	for (int i = 0; i < R; ++i) {
		string row;
		cin >> row;
		board.push_back(row);

		//시작 좌표 찾기
		if ((start.first == -1) && (start.second == -1)) {
			for (int j = 0; j < C; ++j) {
				if (board[i][j] == 'J') {
					start.first = i;
					start.second = j;
					break;
				}
			}
		}

		//불의 좌표 찾기
		for (int j = 0; j < C; ++j) {
			if (board[i][j] == 'F') 
				fire.push_back({ i, j });
		}
	}

	int answer = solve(start.first, start.second);

	if (answer == -1) cout << "IMPOSSIBLE";
	else cout << answer;

	return 0;
}

풀이

• 보드 내 모든 불의 좌표에서 불 확산될 필요 X
  -> 이전 시간에 새로 확산되었던 불의 좌표를 기준으로 확산되면 됨
  -> 보드 내 불의 좌표를 저장하는 벡터(fire) 메모리 초과 문제 해결됨

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int R, C;
vector<string> board;

int dirR[4] = { 0, 1, -1, 0 };
int dirC[4] = { -1, 0, 0, 1 };

bool outOfBoard(int r, int c) {
	if (r < 0 || r >= R) return true;
	if (c < 0 || c >= C) return true;
	return false;
}


//보드 불의 좌표
vector<pair<int, int>> fire;

//보드 불 확산
void boardFire() {
	
	//새로 확산된 불의 좌표
	vector<pair<int, int>> newFire;

	vector<vector<int>> visited(R, vector<int>(C, 0));

	for(int i = 0; i<fire.size(); ++i){
		int curR = fire[i].first;
		int curC = fire[i].second;
		visited[curR][curC] = 1;

		for (int d = 0; d < 4; ++d) {
			int nextR = curR + dirR[d]; 
			int nextC = curC + dirC[d];

			if (outOfBoard(nextR,nextC)) continue;
			if (board[nextR][nextC] == '#') continue;
			if (board[nextR][nextC] == 'F') continue;
			if (visited[nextR][nextC]) continue;
			
			board[nextR][nextC] = 'F';
			newFire.push_back({ nextR, nextC });
		}
	}

	//다음번에 다시 불이 확산되는 경우
	//이번에 새로 확산된 불에서 부터 확산하면 됨
	fire.clear();
	fire.assign(newFire.begin(), newFire.end());

	return;
}

int solve(int startR, int startC) {

	vector<vector<int>> visited(R, vector<int>(C, 0));
	//<-time, 현재 좌표 pair>
	priority_queue<pair<int, pair<int,int>>> q;
	q.push({ 0, {startR, startC} });

	int boardTime = 0;
	while (!q.empty()) {
		int curTime = -q.top().first;
		int curR = q.top().second.first;
		int curC = q.top().second.second;
		q.pop();

		if (visited[curR][curC]) continue;
		visited[curR][curC] = 1;

		while(boardTime < curTime) {
			boardFire();
			boardTime++;
		}
		//현재 위치에 불이 번졌는지 확인!!
		if (board[curR][curC] == 'F') continue;

		for (int d = 0; d < 4; ++d) {
			int nextR = curR + dirR[d];
			int nextC = curC + dirC[d];

			//다음 이동시 보드 밖인 경우 탈출 성공
			if (outOfBoard(nextR, nextC)) {
				return curTime + 1;
			}

			//다음 칸으로 이동
			if (board[nextR][nextC] == '#') continue;
			if (board[nextR][nextC] == 'F') continue;
			if (visited[nextR][nextC]) continue;
			q.push({ -(curTime + 1),{nextR, nextC} });
		}
	}

	//탈출 불가능
	return -1;
}

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

	cin >> R >> C;

	pair<int, int> start = { -1, -1 };

	for (int i = 0; i < R; ++i) {
		string row;
		cin >> row;
		board.push_back(row);

		//시작 좌표 찾기
		if ((start.first == -1) && (start.second == -1)) {
			for (int j = 0; j < C; ++j) {
				if (board[i][j] == 'J') {
					start.first = i;
					start.second = j;
					break;
				}
			}
		}

		//불의 좌표 찾기
		for (int j = 0; j < C; ++j) {
			if (board[i][j] == 'F') 
				fire.push_back({ i, j });
		}
	}

	int answer = solve(start.first, start.second);

	if (answer == -1) cout << "IMPOSSIBLE";
	else cout << answer;

	return 0;
}