글 읽기 - 메모리 초과가 어느 부분에서 일어나는지 모르겠습니다.

angela0102 5년 전 0

결과는 잘 나오는데, 왜 메모리 초과가 나오는지 모르겠습니다..ㅠㅠ

#include <cstdio>
#include <queue>
using namespace std;
struct Map {
	int x, y, w;
};
int n, m, brk, day; //day=0 : 낮, day=1 : 밤
int a[1000][1000], dist[1000][1000][11];
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
int bfs() {
	queue<Map> q;
	q.push({ 0,0,0 });
	dist[0][0][0] = 1;
	day = 0;
	while (!q.empty()) {
		int x = q.front().x, y = q.front().y, w = q.front().w;
		q.pop();
		if (x == n - 1 && y == m - 1) return dist[x][y][w];
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k], ny = y + dy[k];
			if (nx >= 0 && nx < n&&ny >= 0 && ny < m) {
				if (dist[nx][ny][w]) continue;
				if (a[nx][ny] == 0) {
					q.push({ nx, ny, w });
					dist[nx][ny][w] = dist[x][y][w] + 1;
				}
				if (a[nx][ny] == 1&& w < brk) {
					if (day == 0) {
						q.push({ nx, ny, w + 1 });
						dist[nx][ny][w + 1] = dist[x][y][w] + 1;
					}

					else{
						q.push({ x, y, w });
						dist[x][y][w]++;
					}
				}
			}
		}
		day = !day;
	}
	return -1;
}
int main() {
	scanf("%d %d %d", &n, &m, &brk);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &a[i][j]);
	printf("%d\n", bfs());
	return 0;
}

djm03178 5년 전 0

dist[nx][ny][w + 1]이 0이 아니어도 day가 0이면 큐에 또 넣게 됩니다.

angela0102 5년 전 0

dist[nx][ny][w + 1]이 0일때만 지나갈 수 있도록 수정했는데, 이번엔 틀렸다고 합니다ㅠㅠ 아무리봐도원인을 모르겠습니다ㅜㅜ

#include <cstdio>
#include <queue>
using namespace std;
struct Map {
	int x, y, w;
};
int a[1000][1000], dist[1000][1000][11];
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
int n, m, brk;
bool day = true;
int bfs() {
	queue<Map> q;
	q.push({ 0,0,0 });
	dist[0][0][0] = 1;
	while (!q.empty()) {
		int x = q.front().x, y = q.front().y, w = q.front().w;
		q.pop();
		if (x == n - 1 && y == m - 1) return dist[x][y][w];
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k], ny = y + dy[k], nw = w + 1;
			if (nx >= 0 && nx < n&&ny >= 0 && ny < m) {
				if (a[nx][ny] == 0 && dist[nx][ny][w]==0) {
					q.push({ nx, ny, w });
					dist[nx][ny][w] = dist[x][y][w] + 1;
				}
				else if(a[nx][ny]==1 && w < brk && dist[nx][ny][nw]==0){
					if (day) {
						q.push({ nx, ny, nw});
						dist[nx][ny][nw] = dist[x][y][w] + 1;
					}
					else {
						q.push({ x, y, w });
						dist[x][y][w]++;
					}
				}
			}
		}
		day = !day;
	}
	return -1;
}
int main() {
	scanf("%d %d %d", &n, &m, &brk);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%1d", &a[i][j]);
	printf("%d\n", bfs());
	return 0;
}

djm03178 5년 전 1

제가 아까 반례를 잘못 드렸는데, 여기 다시 드립니다.

38번째 줄에서 day가 바뀌는 것이 과연 적절한지 생각해 보세요. 아래 예시의 답은 8입니다.

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

문제

문제

출처

ICPC

메모리 초과가 어느 부분에서 일어나는지 모르겠습니다.

angela0102 5년 전 0

djm03178 5년 전 0

angela0102 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말