글 읽기 - [2589 보물섬] 시간초과 질문드립니다.

10jobss 6년 전 0

배열의 최대 크기가 50*50인걸 고려해 땅(L)인 부분 각각에 대해

bfs를 이용해 최단 거리로 이동하는데 있어 가장 긴 시간 중 최대값을 구하는 방식으로 접근했고 결과는 시간초과입니다.

아래 코드에서 잘못된 부분이 궁금합니다. 더 최적화가 가능한가요? 혹은 접근 방법이 잘못된 것인가요?

정말 알고 싶습니다.

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
int row, col, ans;
char map[51][51];
int dist[51][51];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int bfs(int y, int x) {
	int l = 0;
	queue<pii> q;
	q.push({ y,x });
	while (!q.empty()) {
		int py = q.front().first;
		int px = q.front().second;
		for (int i = 0; i < 4; ++i) {
			int ny = py + dy[i];
			int nx = px + dx[i];
			if (ny<1 || ny>row || nx<1 || nx>col) continue;
			if (map[ny][nx] == 'W') continue;
			if (dist[ny][nx] > 0) continue;
			dist[ny][nx] = dist[py][px] + 1;
			l = max(l, dist[ny][nx]);
			q.push({ ny,nx });
		}
	}
	return l;
}
int main() {
	scanf("%d %d", &row, &col);
	for (int i = 1; i <= row; ++i) {
		char s[51];
		scanf("%s", s);
		for (int j = 0; j < col; ++j) map[i][j + 1] = s[j];
	}
	for (int i = 1; i <= row; ++i) {
		memset(dist, -1, sizeof(dist));
		for (int j = 1; j <= col; ++j) {
			if (map[i][j] == 'L') {
				dist[i][j] = 0;
				int tmp = bfs(i, j);
				ans = max(ans, tmp);
			}
		}
	}
	printf("%d", ans);
	return 0;
}

djm03178 6년 전 1

q.pop ()을 하지 않으면 큐에서 원소가 제거되지 않습니다.

10jobss 6년 전 0

@djm03178 q.pop() 추가했고 dist 배열 초기화 위치랑 bfs 함수 dist[ny][nx]>0 부분도 틀렸었네요. 세 부분 수정해서 AC 받았습니다. 답변 감사합니다!

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

문제

문제

출처

ICPC

[2589 보물섬] 시간초과 질문드립니다.

10jobss 6년 전 0

djm03178 6년 전 1

10jobss 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말