글 읽기 - 로봇 메모리초과이유

cjy0005 4년 전 0

정답 코드와 비교해봐도 도저히모르겠네요 왜 메모리초과가나는지;;;

#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int A[5] = { 0,0,0,1,-1 };
int B[5] = { 0,1,-1,0,0 };
struct AR {
	int x, y, d;
};
int visit[102][102][5] // 1동 2서 3남 4북 visit값은 방향별 총방법수
int N, M;
int map[102][102];
int d[5][5];
int direction(int e, int f) { //e 와 f방향의 차이 1,2이면 두번 명령해야됨으로 2반환
	if (d[e][f]) {
		return 2;
	}
	else {
		if (e - f == 0) {
			return 0;
		}
		else {
			return 1;
		}
	}
}
int start[3];
int en[3];
void BFS() {
	queue<AR>save;
	save.push({ start[0], start[1], start[2] });  //save 큐에 x,y,방향을 넣어준다
	while (!save.empty()) {
		int a = save.front().x;
		int b = save.front().y;
		int c = save.front().d;
		save.pop();
		if (a == en[0] && b == en[1] && c == en[2]) {  //en은 도착지 정보
			cout << visit[en[0]][en[1]][en[2]];
			break;
		}
		for (int i = 1; i <= 3; i++) {   //전진 
			int n, m;
			n = a + A[c] * i;
			m = b + B[c] * i;
			if (n >= 1 && n <= N && m >= 1 && m <= M) { 
				if (!map[n][m]) {
					if (!visit[n][m][c]) {
						visit[n][m][c] = visit[a][b][c] + 1;
						save.push({ n,m,c });
					}
					else {
						continue;
					}
				}
				else {
					break; //못가면 다음 칸도 못감으로 break;
				}
			}
			else {
				break; //못가면 다음 칸도 못감으로 break;
			}
		}
		for (int i = 1; i <= 4; i++) {  //제자리에서 방향전환
			if (c == i) {
				continue;
			}
			if (direction(c, i) == 2) {  //뒤로는 가지않는다.
				continue;
			}
			visit[a][b][i] = visit[a][b][c] + direction(c, i);
			save.push({ a,b,i });
		}
	}
}
int main(void) {
	d[1][2] = 1;  
	d[2][1] = 1;
	d[3][4] = 1;
	d[4][3] = 1;
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < 3; i++) {
		cin >> start[i];
	}
	for (int i = 0; i < 3; i++) {
		cin >> en[i];
	}
	BFS();
	return 0;
}

shin421179 2달 전 0

방향 전환 시에도 이미 더 적은 코스트로 방문했던 곳은 큐에 넣지 않아야 메모리 초과를 피할 수 있습니다.

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

문제

문제

출처

ICPC

로봇 메모리초과이유

cjy0005 4년 전 0

shin421179 2달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말