[BOJ] 4179번 불!(C++)

소요시간 : 2시간 이상

90분정도 걸려서 실수가 없다는 판단을 하고 제출했으나, 메모리 초과가 발생했다.
아직 구현하는데 시간이 많이걸리는 것 같다. 메모리 초과가 발생한 이유는 사소한 실수라기 보다는 방법론적인 차이가 있었다. 문제를 쉽게 풀어내지는 못했지만, 얻어가는 내용 위주로 기록한다.

두개의 존재가 동시에 좌표상에서 움직이는 경우

내가 설계한 코드는 불의 전이와 지훈이의 이동을 번갈아가면서 실행했다. 아마도 메모리 초과의 가장 큰 원인이 아니였나 싶은데, 애초에 불의 전이속도를 기록한 MAP 을 만들어놓고 이를 바탕으로 비교하면서 지훈이를 이동시키는 것이 현명한 설계였던 것 같다.

초기 배열의 MAX 값 설정

위의 설계를 수정하여 코드를 제출했는데 실행 60% 쯤 오류가 발생했다. Fired 라는 배열은 해당 칸에 불이 몇 초만에 도착하는지를 기록하는 배열인데, 초기 값은 0으로 세팅되어있다. 지훈이가 이동한 칸에 불보다 빨리 도착하면 큐에 정보를 저장하는 방식인데, 일단 앞선 IF 문을 다 통과하면 Fired 배열 값으로 인한 문제가 발생하지 않을 것이라 생각했다. MAX 값을 세팅하니 문제가 해결되었고, 이는 조금 더 고찰이 필요한 부분이다.

-> 문제 풀이를 많이 검색해본 결과, 거리를 저장하는 배열의 초기화는 -1 이나 MAX 로 설정하는것이 정석적인 풀이방식인 것 같다.

전체 코드

#include<iostream>
#include<queue>
using namespace std;
#define MAX 987654321

int R, C;
char Map[1001][1001];
int Visit[1001][1001];
// 지훈 방문 여부

int Fired[1001][1001];
int Fired_Visit[1001][1001];
// 불의 지도

int Dx[4] = { 1, -1, 0, 0 };
int Dy[4] = { 0, 0, 1, -1 };


struct fire {
	int x;
	int y;
	int time;
};
queue<fire> Fire_Q;


struct jhoon {
	int x;
	int y;
	int time;
};
queue<jhoon> Q;


// 입력 값을 받는다.
void Input() {

	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> Map[i][j];
			Fired[i][j] = MAX;

			if (Map[i][j] == 'F') {
				// 시작 타임 : 0
				Fired_Visit[i][j] = 1;
				Fired[i][j] = 0;
				Fire_Q.push({ i, j, 0 });
			}

			if (Map[i][j] == 'J') {
				Visit[i][j] = 1;
				// 시작 타임 : 0
				Q.push({ i, j, 0 });
			}

		}
	}

}



// 불의 지도를 완성한다.
void Fire_Spread() {

	while (!Fire_Q.empty()) {

		int px = Fire_Q.front().x;
		int py = Fire_Q.front().y;
		int time = Fire_Q.front().time;
		Fire_Q.pop();

		for (int i = 0; i < 4; i++) {

			int nx = px + Dx[i];
			int ny = py + Dy[i];

			if (nx < 1 || ny < 1 || nx > R || ny > C) continue;				// 범위 초과
			if (Map[nx][ny] == '#' || Fired_Visit[nx][ny] == 1) continue;	// 벽

			Fired_Visit[nx][ny] = 1;
			Fired[nx][ny] = Fired[px][py] + 1;
			Fire_Q.push({ nx, ny, time + 1 });

		}

	}

}



// 지훈이의 이동
int Bfs() {

	while (!Q.empty()) {

		int px = Q.front().x;
		int py = Q.front().y;
		int time = Q.front().time;
		// 시작 시간 : 0 
		Q.pop();


		if (px == 1 || px == R) return (time + 1);
		if (py == 1 || py == C) return (time + 1);
		// 탈출 성공

		for (int i = 0; i < 4; i++) {

			int nx = px + Dx[i];
			int ny = py + Dy[i];
			int nTime = time + 1;

			if (nx < 1 || ny < 1 || nx > R || ny > C) continue;				// 범위 초과
			if (Map[nx][ny] == '#' || Map[nx][ny] == 'F') continue;			// 불 & 벽
			if (Visit[nx][ny] == 1) continue;								// 방문 노드 & 불에 탄 노드

			if (nTime < Fired[nx][ny]) {
				Visit[nx][ny] = 1;
				Q.push({ nx, ny, nTime });
			}
		}

	}
	
	return -1;

}



int main() {

	Input();
	Fire_Spread();
	int ans = Bfs();
	if (ans == -1) {
		cout << "IMPOSSIBLE" << endl;
	}
	else {
		cout << ans << endl;
	}

}