글 읽기 - 시간초과가 떴습니다. 좋은 방법 없을까요?

kangsy763 4년 전 0

문제 풀면서도 시간초과가 나올 것 같다는 생각은 했는데 역시나 시간초과가 나와버렸네요..

box 를 한 번 훑어서 1들을 queue 에다가 집어넣고 그 주위에 0인것들을 1로 바꿉니다. 그리고 바꾸고 난 후의 1들의 숫자들을 cnt 해서

이전에 돌았을 때의 cnt와 비교해서 같다면 -1이 나오게 했습니다. 그렇게 반복하다가 box를 모두 체크햇는데 0이없으면 그 때의 day를 출력하는 식입니다.

시간초과가 결국 떠버렸네요... 좋은 해결방안이 있을까요 ? 이 코드는 bfs 함수 내의 for문 2중으로 돌리는 부분 떄문에 시간초과가 나는 것 같은데요..

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int box[1001][1001];
int n, m;
int cnt = 0;
int m_cnt = 0;

void bfs() {
	int x, y;
	queue<pair<int, int> >q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (box[i][j] == 1) {
				q.push(make_pair(i, j));
			}
		}
	}
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx > 0 && xx <= n && yy > 0 && yy <= m&&box[xx][yy]==0) {
				box[xx][yy] = 1;
				cnt++;
			}
		}
	}
}

int main() {
	int flag = 0;
	int day = 0;
	scanf("%d %d", &m, &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &box[i][j]);
			if (box[i][j] == 1) cnt++;
			if (box[i][j] == (-1)) m_cnt++;
		}
	}
	if (cnt == m * n - m_cnt) {
		printf("0");
		return 0;
	}
	while (true) {
		int temp = cnt;
		bfs();
		day++;
		if (cnt == m * n - m_cnt) {
			printf("%d", day);
			return 0;
		}
		if (temp == cnt) {
			printf("-1");
			return 0;
		}
	}
	return 0;
}

kangsy763 4년 전 0

자문 자답합니다. 16~22 번 줄을 넣은 이유는 1의 위치가 어디있는지 파악하기 위함이었습니다.

그런데, 애초에 입력을 받을 때에 1일 때에 바로 push를 해주면 되는 거였습니다.... 그것과 더불어 코드 이것저것 고쳤더니 통과했습니다.

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

queue<pair<int, int> >q;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int box[1001][1001];
int n, m;
int cnt = 0;
int m_cnt = 0;

void bfs() {
	int x, y;
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx > 0 && xx <= n && yy > 0 && yy <= m&&box[xx][yy]==0) {
				box[xx][yy] = box[x][y] + 1;
				q.push(make_pair(xx, yy));
			}
		}
	}
}

int main() {
	scanf("%d %d", &m, &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &box[i][j]);
			if (box[i][j] == 1) {
				cnt++;
				q.push(make_pair(i, j));
			}
			if (box[i][j] == (-1)) m_cnt++;
		}
	}

	bfs();
	int max = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (box[i][j] == 0) {
				printf("-1");
				return 0;
			}
			if (box[i][j] > max) max = box[i][j];
		}
	}
	printf("%d", max-1);
	return 0;
}

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

문제

문제

출처

ICPC

시간초과가 떴습니다. 좋은 방법 없을까요?

kangsy763 4년 전 0

kangsy763 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말