글 읽기 - 2206 벽부수고 이동하기 메모리초과..

cxz5309 6년 전 0

3차원 배열으로 풀란 소리를 들은 것 같아서 그렇게 풀었는데 그게 잘못된 건가요?

아니면 어떤 조건을 추가하면 메모리 초과가 안나는건가요?

​#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef struct sss{
	int x, y,d,count;
}S;

int m, n;
int zone[1001][1001];
int chk[1001][1001][2];
int itx[4] = { 1, 0, -1, 0 };
int ity[4] = { 0, 1, 0, -1 };
int flag;

int range(int x, int y) {
	if (x >= 0 && x < m&&y >= 0 && y < n)
		return 1;
	else
		return 0;
}

void bfs() {
	queue<S>q;
	q.push({ 0, 0, 0, 0 });
	chk[0][0][0] = 1;
	while (!q.empty()) {
		S tmp;
		tmp = q.front();
		q.pop();
		if (tmp.x == m - 1 && tmp.y == n - 1) {
			printf("%d", tmp.count+1);
			flag = 1;
			break;
		}
		for (int i = 0; i < 4; i++) {
			S next;
			next.x = tmp.x + itx[i];
			next.y = tmp.y + ity[i];
			next.d = tmp.d;
			next.count = tmp.count + 1;
			if (range(next.x, next.y) == 1) {
				if (zone[next.y][next.x] == 0) {
					if (next.d == 0) {
						chk[next.y][next.x][0] = 1;
					}
					else if (next.d == 1){
						chk[next.y][next.x][1] = 1;
					}
				}
				else if (zone[next.y][next.x] == 1 && tmp.d == 0) {
					next.d = tmp.d + 1;
					chk[next.y][next.x][1] = 1;
				}
				q.push(next);
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &zone[i][j]);
		}
	}
	bfs();
	if (flag == 0)
		printf("-1");
}

djm03178 6년 전 0

이 코드는 갈 수만 있으면 무조건 큐에 추가해버리게 되는데, 이미 방문한 곳은 다시 방문할 필요가 없습니다. 중복 방문과 함께 큐에 들어가는 원소가 기하급수적으로 늘어나기 때문에 메모리 초과가 납니다.

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

문제

문제

출처

ICPC

2206 벽부수고 이동하기 메모리초과..

cxz5309 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말