백준 4179 C++

백준 4179

나는 0~R, 0~C로 범위를 잡으니 그 범위로 나가는 최단 경로를 찾으면 된다. 최단 경로를 찾는 거니까 bfs로 해야하는데 내가 한 풀이는 시간초과가 떴다.

내가 푼 시간 초과 코드는 이렇다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;


int R, C;

char map[1001][1001], mmap[1001][1001];

bool visited[1001][1001];


void maptommap() {
	for (int y = 0; y < R; ++y) {
		for (int x = 0; x < C; ++x) {
			mmap[y][x] = map[y][x];
		}
	}
}

void mmaptomap() {
	for (int y = 0; y < R; ++y) {
		for (int x = 0; x < C; ++x) {
			map[y][x] = mmap[y][x];
		}
	}
}

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

void printmap() {
	for (int y = 0; y < R; ++y) {
		for (int x = 0; x < C; ++x) {
			cout << map[y][x];
		}
		cout << "\n";
	}
}

void burn() {
	maptommap();


	for (int y = 0; y < R; ++y) {
		for (int x = 0; x < C; ++x) {
			if (map[y][x] == 'F') {
				for (int i = 0; i < 4; i++) {
					int ny = y + dy[i];
					int nx = x + dx[i];

					if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
					if (mmap[ny][nx] != '#' && mmap[ny][nx] != 'F') {
						mmap[ny][nx] = 'F';
					}
				}
			}
		}
	}

	mmaptomap();
	//printmap();
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> R >> C;
	for (int y = 0; y < R; ++y) {
		for (int x = 0; x < C; ++x) {
			cin >> map[y][x];

			if (map[y][x] == 'J') {
				sy = y;
				sx = x;
			}
		}
	}

	//priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> que;
	queue< pair<int, pair<int, int>>> que;
	que.push({ 0,{sy,sx} });
	visited[sy][sx] = true;

	int curTime = 0;

	while (!que.empty()) {
		int cur = que.front().first;
		int y = que.front().second.first;
		int x = que.front().second.second;

		//cout << y << " " << x << " " << cur << " \n";
		
		que.pop();

		if (y < 0 || y >= R || x < 0 || x >= C) {
			cout << cur;
			return 0;
		}
		
		if (curTime < cur) {
			curTime = cur;
			burn();
		}

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

			int ny = y + dy[i];
			int nx = x + dx[i];

			if (map[ny][nx] != '#' && map[ny][nx] != 'F') {
				if (!visited[ny][nx]) {
					//cout << 1 << "\n";
					que.push({ cur + 1, {ny, nx} });
					visited[ny][nx] = true;
				}
			}
		}

	}
	
	cout << "IMPOSSIBLE";

	return 0;
}

그 이유는 한 타임이 넘어갈 때마다 불을 늘려주는데, map을 따로 복사한다. 따라서 최대 200만의 호출이 나고 1초당 1억번 계산이라고 생각한 BOJ특성상 시간이 50초만 넘어가더라도 시간초과가 뜨는 것이다.

2%에서 시간 초과가 떠서, 알고리즘 자체를 바꾸어야 한다고 생각을 했고… 풀이를 생각해내지 못해서 다른 분들의 코드를 보았다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;


int R, C;

char map[1001][1001];
int times[1001][1001];

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

queue<pair<int, int>> J, F;



void burn() {

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

	cin >> R >> C;
	for (int y = 0; y < R; ++y) {
		for (int x = 0; x < C; ++x) {
			cin >> map[y][x];

			if (map[y][x] == 'J') {
				J.push({ y,x });
				times[y][x] = -1;
			}
			if (map[y][x] == 'F') {
				F.push({ y,x });
			}
			else {
				times[y][x] = -1;
			}
		}
	}
	//불과 플레이어 의 큐를 따로따로. 

	while (!F.empty()) {
		int y = F.front().first;
		int x = F.front().second;

		F.pop();

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

			if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
			if (map[ny][nx] == '#') continue;
			if (times[ny][nx] != -1) continue;
			times[ny][nx] = times[y][x] + 1;//먼저 불의 확산을 구해서, 불이 그 위치에 닿는 시간을 구함. 
			F.push({ ny,nx });
		}
	}
	

	times[J.front().first][J.front().second] = 0;//캐릭터의 타임. 캐릭터가 현재 위치에 도달할 수 있는 시간을 구함. 
	while (!J.empty()) {
		int y = J.front().first;
		int x = J.front().second;

		J.pop();

		int ncur = times[y][x] + 1;

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

			if (ny < 0 || ny >= R || nx < 0 || nx >= C) {
				cout << ncur;
				return 0;
			}

			if (map[ny][nx] == '#')continue;
			if (times[ny][nx] != -1 && times[ny][nx] <= ncur) continue;
			times[ny][nx] = ncur;
			J.push({ ny, nx });//캐릭터가 기존에 입력된 데이터(불)보다 빨리 도달할 수 있으면 큐에 추가. 
		}
	}
	cout << "IMPOSSIBLE";

	return 0;
}

풀이는 이렇다.

times에 불이 그 좌표에 닿는 시간을 bfs를 통해 기록해놓는다.

그 이후, J좌표에서 시작해서 J가 그 좌표에 닿는 시간을 계산한 후, 기존에 저장된 데이터(불이 닿는 최소시간)보다 빠르게 닿는다면 그것을 유망하다고 판단 후, 큐에 넣는다. 그렇게 바깥에 닿으면 바로 출력해서 프로그램을 종료하면 끝.

BOJ 카테고리 내 다른 글 보러가기