글 읽기 - 메모리 사용관련해서 질문있습니다.

jokerkwu 5년 전 0

주석처리한 코드와 주석처리하지 않은 코드가 푸는 방식이 거의 같다고 봐도 될거같은데 차이점이라면 주석처리한 코드는 Point로 좌표를 나타내고 주석처리하지않은 코드는 pair를 사용해서 좌표를 나타낸부분만 다르게 보이는데요. 주석처리한 코드는 통과되고 주석처리되지 않은 코드는 메모리초과가 뜨는데 그이유를 알 수 있을까요? 어느 부분에서 메모리 사용을 잘못했는지 알고 싶습니다.

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
#define MAX 31
char board[MAX][MAX][MAX];
bool visited[MAX][MAX][MAX];
//거리 층, y축 x축
typedef pair<int, pair<int, pair<int, int>>> piiii;
int dx[6] = { 0,0,1,0,-1,0 };
int dy[6] = { 0,0,0,1,0,-1 };
int dz[6] = { 1,-1,0,0,0,0 };
int bfs(int sl,int sr,int sc,int l, int r, int c) {
	queue<piiii>pq;//거리랑 이동좌표
	pq.push(make_pair(0, make_pair(sl,make_pair(sr,sc))));
	while (!pq.empty()) {
		int curD = pq.front().first;
		int curL = pq.front().second.first;
		int curR = pq.front().second.second.first;
		int curC = pq.front().second.second.second;
		visited[curL][curR][curC] = true;
		pq.pop();
		if (board[curL][curR][curC] == 'E') {
			return curD;
		}
		for (int i = 0; i < 6; i++) {
			int nextL = curL + dz[i];
			int nextR = curR + dy[i];
			int nextC = curC + dx[i];
			int nextD = curD + 1;
			if (board[nextL][nextR][nextC] == '.'||board[nextL][nextR][nextC]=='E') {
				if (nextL > 0 && nextR > 0 && nextC > 0 && nextL <= l && nextR <= r && nextC <= c && !visited[nextL][nextR][nextC]) {
					pq.push(make_pair(nextD, make_pair(nextL, make_pair(nextR, nextC))));
				}
			}
		}
	}
	return 0;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int l, r, c;
	cin >> l >> r >> c;
	while (l != 0 && r != 0 && c != 0) {
		memset(board, '\0', sizeof(board));
		memset(visited, false, sizeof(visited));
		int startL, startR, startC;
		for (int k = 1; k <= l; k++) {
			for (int i = 1; i <= r; i++) {
				for (int j = 1; j <= c; j++) {
					cin >> board[k][i][j];
					if (board[k][i][j] == 'S') {
						startL = k; startR = i; startC = j;
					}
				}
			}
		}
		int res = 0;
		res=bfs(startL, startR, startC,l,r,c);
		if (res != 0) {
			printf("Escaped in %d minute(s).\n", res);
		}
		else {
			printf("Trapped!\n");
		}
		
		cin >> l >> r >> c;
	}
	return 0;
}

/*


​
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
​
​
struct Point {
	int z; int y; int x;
	Point(int a, int b, int c) { z = a; y = b; x = c; };
	Point() {};
};
​
int l, r, c;
int dx[] = { 1, -1, 0, 0, 0, 0 };
int dy[] = { 0, 0, 1, -1, 0, 0 };
int dz[] = { 0, 0, 0, 0, 1, -1 };
const int INF = 2e9;
Point sp, ep;
​
int main(void) {
	while (true) {
​
		char a[30][30][30];
		int visited[30][30][30] = { 0, };
​
		scanf("%d %d %d", &l, &r, &c);
​
		if (!l && !r && !c) break;
​
		for (int i = 0; i < l; i++) {
			for (int j = 0; j < r; j++) {
				scanf("%s", a[i][j]);
				for (int k = 0; k < c; k++) {
					if (a[i][j][k] == 'S') {
						sp = Point(i, j, k);
					}
					if (a[i][j][k] == 'E') {
						ep = Point(i, j, k);
					}
				}
			}
			getchar();
		}
​
		queue<Point> q;
		q.push(sp);

		while (!q.empty()) {
			auto cur = q.front(); q.pop();
			int cl = cur.z;
			int cr = cur.y;
			int cc = cur.x;

			for (int i = 0; i < 6; i++) {
				int nl = cl + dz[i];
				int nr = cr + dy[i];
				int nc = cc + dx[i];
​
				if (nl >= l || nr >= r || nc >= c || nl < 0 || nr < 0 || nc < 0) continue;
				if (visited[nl][nr][nc]) continue;
				if (a[nl][nr][nc] == '#') continue;
​
				visited[nl][nr][nc] = visited[cl][cr][cc] + 1;
				q.push(Point(nl, nr, nc));
			}
		}
​
		if (visited[ep.z][ep.y][ep.x] > 0) {
			printf("Escaped in %d minute(s).\n", visited[ep.z][ep.y][ep.x]);
		}
		else {
			printf("Trapped!\n");
		}
	}
​
	return 0;
}
​
*/

djm03178 5년 전 0

%s로 길이 30의 문자열을 저장하려면 최소 31칸이 필요합니다.

jokerkwu 5년 전 0

댓글달아주셔서 감사합니다. 주석처리 되어있지 않는 코드가 메모리 초과가 났구요. 주석처리한 코드가 통과했는데 다른 이유가 있을까요?

djm03178 5년 전 0

BFS는 큐에서 뺀 다음에 방문 체크를 하는 것이 아니라 큐에 넣을 때 해야 합니다. 여러 정점에서 한 정점을 동시에 방문하려고 할 수 있기 때문입니다.

jokerkwu 5년 전 0

헉.... 여태까지 BFS 구현을 이상하게 하고있었네요.. 정말 감사합니다.!!

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

문제

문제

출처

ICPC

메모리 사용관련해서 질문있습니다.

jokerkwu 5년 전 0

djm03178 5년 전 0

jokerkwu 5년 전 0

djm03178 5년 전 0

jokerkwu 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말