글 읽기 - 메모리 초과.... 한번만 봐주세요.. 제발 ㅠ

carpediem804 4년 전 0

메모리 초과가 뜨는데 왜 뜨는지 이해가 안갑니다 .....

코드 설명을 드리면

초기 water queue -> x가 아닌 모든 점을 넣고

water bfs() - > water queue 사이즈만큼 한번만 도는데 x가 발견되면 그점 0으로 바꾸고 water queue에 넣습니다

findbirdbfs() - > 새의 한점을 bird queue 에 넣고 bfs를 돕니다 ,만약 endx endy 다른 백조를 찾는다면 ans에 시간을 넣고 return 시킵니다 , visit[][]안에는 time 숫자를 넣어서 visit배열 초기화 시키지 않았습니다 .

아무리 생각해도 왜 메모리 초과가 뜨는지 이해가 안갑니다... 도와주세요

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int R, C;
int map[1501][1501];
int visit[1501][1501];
queue<pair<int, int> > water, findbird; //물인점 , 새점
int time;
int ans=-1;
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
int startx, starty;
int endx, endy;
void waterbfs() { //녹는 점찾는 bfs
	int watersize = water.size();

	for (int k = 0; k < watersize; k++) { //지금 q사이즈만큼만 돈다 ! !! -> queue에 추가되는 것은 안돈다
		int x = water.front().first;
		int y = water.front().second;
		water.pop();
		for (int i = 0; i < 4; i++) {
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			if (dx >= 1 && dx <= R && dy >= 1 && dy <= C) {
				if (map[dx][dy] == -1) { //만약 x이면 그점 녹는다 
					map[dx][dy] = 0;
					water.push(make_pair(dx, dy)); //녹는점을 queue에 추가
				}
				
			}
		}
	}
}
void findbfs(int stx, int sty) {

	findbird.push(make_pair(stx, sty)); //시작점을 항상 처음으로 q에 넣는다

	while (findbird.size() != 0) {
		int x = findbird.front().first;
		int y = findbird.front().second;
		findbird.pop();
		if (x == endx && y == endy) {
			ans = time - 1;
			return;
		} //찾았으면 정답 구하고 리턴 
		visit[x][y] = time; // time을 배열에다가 넣는다 -> 초기화 안해도됨
		for (int i = 0; i < 4; i++) {
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			if (dx >= 1 && dx <= R && dy >= 1 && dy <= C) {
				if (visit[dx][dy] != time && map[dx][dy]==0) {
					findbird.push(make_pair(dx, dy));
				}
			}
		}
	}
}
int main(void) {
	scanf("%d %d", &R, &C);
	int ck = 0;
	for (int x = 1; x <= R; x++) {
		for (int y = 1; y <= C; y++) {
			char temp;
			scanf(" %1c", &temp);
			if (temp == 'L') { 
				if (ck == 0) {
					startx = x;
					starty = y;
					ck = 1;
				}
				else {
					endx = x;
					endy = y;
				}
			}
			if (temp == 'X') { 
				map[x][y] = -1; //x인 점은 -1로 통일 
			}
			else { 
				water.push(make_pair(x, y)); // 모든 물을 water에 넣는다
				map[x][y] = 0; 
			}
		}
	}//map 그렷다 
	time = 1;
	while (1) {
		findbfs(startx,starty); //백조 연결되는지 찾는것 
		if (ans != -1) {
			break;
		}
		waterbfs();
		time++;
	}
	printf("%d\n", ans);
	return 0;
}

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

문제

문제

출처

ICPC

메모리 초과.... 한번만 봐주세요.. 제발 ㅠ

carpediem804 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말