글 읽기 - 메모리 초과 문제좀 도와주세요 ㅠ

kokoxg2 7년 전 0

안녕하세요 ! 메모리 초과때문에 머리가 아픈 1인입니다.

먼저 아래 소스를 VS 스냅샷을 찍어서 확인해보면 메모리는 약 500KB정도 사용된다고 나옵니다. 128MB에 비하면...

프로그램 구동 방식을 설명하자면

저는 미로사이즈를 N+1, M+1로 잡았는데 그 이유는 IF문을 조금 간소화하기 위해서 겉테두리?를 추가했습니다.

그리고 IF문을 통해 갈 수 있는 위치를 Queue에 넣은 다음 방문했던 위치를 0 (False) 로 만듭니다.

또 마지막 지점에 못가는 경우가 없기에 위의 과정을 반복하다가 마지막 위치가 방문되면 while문을 종료합니다.

한칸당 if문을 4번 사용하는데, 4(N x M)만큼 IF문을 사용하게 되는데 음.. 메모리가 어디서 많이 사용되는지를 잘 모르겠습니다.

고수님들 조언좀 해주시면 감사하겠습니다 ㅠ_ㅠ

#include <stdio.h>
#include <queue>
using namespace std;

class Mpair {
public:
 int x;
 int y;
 int count;
 Mpair() {}
 Mpair(int _x, int _y, int _count = 0) { x = _x, y = _y, count = _count; }
 Mpair(const Mpair& mpair) { x = mpair.x; y = mpair.y; count = mpair.count; }
};

int maze[101][101];
 queue<Mpair> que;
int n, m;

int main() {
 scanf("%d %d", &n, &m); //  N과 M 입력
    
 for (int i = 1; i <= n; ++i)  // 미로 입력
  for (int j = 1; j <= m; ++j)
   scanf("%1d", &maze[i][j]);
    
 que.push(Mpair(1, 1, 1)); // 시작점 (1,1)을 Queue에 입력
 
while (maze[n][m] == 1) {
    
      Mpair tmp(que.front());
      
      if (maze[tmp.x - 1][tmp.y] == 1)
         que.push(Mpair(tmp.x - 1, tmp.y, tmp.count + 1));
      if (maze[tmp.x + 1][tmp.y] == 1)
         que.push(Mpair(tmp.x + 1, tmp.y, tmp.count + 1));
      if (maze[tmp.x][tmp.y - 1] == 1)
         que.push(Mpair(tmp.x, tmp.y - 1, tmp.count + 1));
      if (maze[tmp.x][tmp.y + 1] == 1)
         que.push(Mpair(tmp.x, tmp.y + 1, tmp.count + 1));
  
      maze[tmp.x][tmp.y] = 0;
      que.pop();
 }
 printf("%d", que.front().count);
 return 0;
}
​

sung1104hyun 7년 전 0

if문 쓰실 때 배열 인덱스 초과할거 같아요. tmp.x + 1 < m? 이런식으로 조건 달아주시는게...

그리고 BFS는 한 step씩 뻗어나가는데 할때마다 0으로 바꾸면 제대로 안돌아갈거 같아요. 방문체크용 배열을 하나 더 잡으시는게 좋을거같네요

kokoxg2 7년 전 0

이런 식으로 바꿨는데도 28%부분에서 메모리 초과가 나네요 읔.. 더 생각해봐야겠어요

if (0 < tmp.x - 1 && isVisit[tmp.x - 1][tmp.y] == 1) // 상
			que.push(Mpair(tmp.x - 1, tmp.y, tmp.count + 1));
		if (tmp.x + 1 <= n && isVisit[tmp.x + 1][tmp.y] == 1) // 하
			que.push(Mpair(tmp.x + 1, tmp.y, tmp.count + 1));
		if (0 < tmp.y - 1 && isVisit[tmp.x][tmp.y - 1] == 1) // 좌
			que.push(Mpair(tmp.x, tmp.y - 1, tmp.count + 1));
		if (tmp.y + 1 <= m && isVisit[tmp.x][tmp.y + 1] == 1) // 우
			que.push(Mpair(tmp.x, tmp.y + 1, tmp.count + 1));

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

문제

문제

출처

ICPC

메모리 초과 문제좀 도와주세요 ㅠ_ㅠ

kokoxg2 7년 전 0

sung1104hyun 7년 전 0

kokoxg2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말