글 읽기 - [c++] 탈출 BFS 메모리 초과 문제

201116313 5년 전 0

요즘 bfs 연습하고 있는데, 이번엔 메모리 초과가 나네요

제 때 pop을 하고 있다고 생각했는데 제출하면 메모리 초과가 나네요...

문제에서 주어진 테스트케이스는 원하는 출력값이 나오기는 합니다.

세시간 동안 다시 작성하고 그랬는데 무엇이 문제인지 모르겠네요..

알려주시면 감사하겠습니다.

/*
3055번 탈출 bfs활용
==입력==
R: 행 C: 열
. : 비어있는 곳 /  X : 돌 / * : 물 / D : 비버의 굴(목표점) / S : 고슴도치의 위치
물: 돌과 비버의 굴을 통과할 수 없음
고슴도치: 돌을 통과할 수 없음
물과 고슴도치는 위 / 아래 / 좌 / 우로 움직일 수 있음.
주의할 점: 고슴도치는 물이 찰 예정인 칸으로 움직일 수 없음.

//

*/
#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

typedef pair<int, int> _defPair;
char map[51][51];
int v[51][51] = { 0 };
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
queue<_defPair>waterQ; // 물에관한 큐
queue<_defPair>q; // 고슴도치에 관한 큐
int R, C, cnt;
_defPair goal;

bool bfs() {
	_defPair loc;

	if (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && nx >= 0 && ny < R && nx < C) {
				if (map[ny][nx] == '.') {
					v[ny][nx] = v[y][x] + 1;
					q.push(make_pair(ny, nx));
					loc.first = ny;
					loc.second = nx;
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			int ny = loc.first + dy[i];
			int nx = loc.second + dx[i];
			if (ny == goal.first && nx == goal.second) {
				v[ny][nx] = v[loc.first][loc.second] + 1;
				return true;
			}
		}
	}
	return false;
}
void waterBfs() {
	if (!waterQ.empty()) {
		int y = waterQ.front().first;
		int x = waterQ.front().second;
		waterQ.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && nx >= 0 && ny < R && nx < C) {
				if (map[ny][nx] == '.') {
					map[ny][nx] = '*';
					waterQ.push(make_pair(ny, nx));
				}
			}
		}
	}
}

int main() {
	int x, y, max = 0;
	bool flag;
	_defPair loc;
	// 입력
	scanf("%d %d", &R, &C);
	for (y = 0; y < R; y++) {
		scanf("%s", &map[y]);
		for (x = 0; x < C; x++) {
			if (map[y][x] == '*') waterQ.push(make_pair(y, x));
			else if (map[y][x] == 'S') {
				q.push(make_pair(y, x));
				v[y][x] = 1;
			}
			else if (map[y][x] == 'D') {
				goal.first = y;
				goal.second = x;
			}
		}
	}

	while (true) {
		if (q.size() == 0) {
			printf("KAKTUS");
			break;
		}

		waterBfs();
		flag = bfs();
		if (flag) {
			break;
		}
	}
	for (y = 0; y < R; y++) {
		for (x = 0; x < C; x++) {
			if (max < v[y][x]) {
				max = v[y][x];
			}
		}
	}
	if (flag == true)
		printf("%d", max - 1);



	return 0;
}

djm03178 5년 전 2

v에 열심히 방문 기록을 적고는 있는데, 기록이 되어있는지 실제로 확인을 하지 않으니 결국 중복 방문이 계속해서 일어나게 됩니다.

201116313 5년 전 0

저번에도 그렇고 지적해주셔서 감사합니다. 저것말고 여러가지 경우의 수 상황들을 추가로 고려해서 수정해보겠습니다.

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

문제

문제

출처

ICPC

[c++] 탈출 BFS 메모리 초과 문제

201116313 5년 전 0

djm03178 5년 전 2

201116313 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말