글 읽기 - 불 문제 시간초과 질문입니다

shinyou1024 4년 전 0

3055번 탈출 문제처럼 각 칸에 불이 언제 번지는지 먼저 기록해두고

또 BFS를 돌려서 불이 번지기 전에 해당 칸을 방문할 수 있으면 큐에 넣어주는 방식으로 접근했습니다.

25%쯤에서 시간초과가 나는데 혹시 수정해야할 부분이 있을까요?

조언 부탁드립니다!

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
struct Pos{
	int y;
	int x;
	int t;
	Pos(int y, int x, int t) : y(y), x(x), t(t) {}
};
int T, w, h;
char map[1000 + 1][1000 + 1];
int fire[1000 + 1][1000 + 1];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int ans;
void init() {
	memset(fire, -1, sizeof(fire));
	ans = -1;
}
void bfs_fire(int y, int x) {
	queue<Pos> q;
	int visit[1000 + 1][1000 + 1];
	memset(visit, 0, sizeof(visit));

	q.push(Pos(y, x, 0));
	visit[y][x] = 1;

	while (!q.empty()) {
		y = q.front().y;
		x = q.front().x;
		int t = q.front().t;
		q.pop();
		if (fire[y][x]==-1 || t < fire[y][x]) {
			fire[y][x] = t;
		}
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny<0 || ny>h - 1 || nx<0 || nx>w - 1)
				continue;
			if (visit[ny][nx])
				continue;
			if (map[ny][nx] == '#' || map[ny][nx] == '*')
				continue;
			visit[ny][nx] = 1;
			q.push(Pos(ny, nx, t + 1));
		}
	}

}
int bfs_escape(int y, int x) {
	queue<Pos> q;
	int visit[1000 + 1][1000 + 1];
	memset(visit, 0, sizeof(visit));

	q.push(Pos(y, x, 0));
	visit[y][x] = 1;
	while (!q.empty()) {
		y = q.front().y;
		x = q.front().x;
		int t = q.front().t;
		q.pop();

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

			// 탈출

			if (ny<0 || ny>h - 1 || nx<0 || nx>w - 1) {
				return time;
			}
			if (visit[ny][nx])
				continue;
			if (map[ny][nx] == '#')
				continue;
			if (map[ny][nx] == '*')
				continue;
			if (fire[ny][nx] > time) {
				visit[ny][nx] = 1;
				q.push(Pos(ny, nx, time));
			}

		}
	}
	return -1;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> T;
	for (int tc = 0; tc < T; tc++) {
		init();
		cin >> w >> h;
		int sy, sx;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[i][j];
				if (map[i][j] == '@') {
					sy = i;
					sx = j;
				}
			}
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == '*') {
					bfs_fire(i, j);
				}
			}
		}
		ans = bfs_escape(sy, sx);
		if (ans == -1)
			cout << "IMPOSSIBLE" << '\n';
		else
			cout << ans << '\n';
	}
	return 0;
}

newdeal 4년 전 0

안녕하세요.

다음 같은 케이스를 생각해보면,

5 5

@****

*****

109줄~110줄에서 *인 모든점에대해 bfs를 각각 돌리고 있습니다. 이 케이스같이 @를 뺀 나머지점이 모두*인 케이스 에서는

w*h개의 점에서 w*h만큼의 시간복잡도가 소요되어 O((w*h)^2)만큼의 시간복잡도를 가지게 됩니다.

맨처음 입력받을때 불의 좌표를 모두 저장해 둔 다음, 한꺼번에 큐에넣고 bfs를 돌리면 어떨까요?

shinyou1024 4년 전 0

답변 감사합니다!

fire[ny][nx] 가 초기값이거나 해당 칸을 기록보다 더 일찍 방문하게 되면

큐에 넣어주는 방식으로 bfs를 수정해보고 있습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

불 문제 시간초과 질문입니다

shinyou1024 4년 전 0

newdeal 4년 전 0

shinyou1024 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말