글 읽기 - 메모리 초과 문제입니다.

daezang102 2년 전 0

기존까지 bfs문제 풀면서 메모리 초과 문제가 발생한적은 없었는데

메모리 초과 문제가 발생하네요. 알고리즘 문제같은데

20~31 줄이 메모리초과의 주된 원인처럼 보이는데, 정확하게 아는 개념이 없다보니 이해가 가지 않네요.

AC풀이들도 저랑 비슷한것 같구요..

공간복잡도에 관해 무지한 저에게 가르침 부탁드립니다... ㅠㅠ

#include<iostream>
#include<queue>
#define MAX 1000001
using namespace std;
int F,S,G,U,D;
// 총,지금,목표,위로,아래로
bool visited[MAX]={false};
int arr[MAX];

void bfs(){
    queue<int> q;
    q.push(S);
    while(!q.empty()){
        int now = q.front();
        visited[now] = true;
        if(now == G) break;
        q.pop();
        int up = now + U;
        int down = now - D;
        if(down > 0){
            if(!visited[down]){
                q.push(down);
                arr[down] = now;
            }
        }
        if(up <= F){
            if(!visited[up]){
                q.push(up);
                arr[up] = now;
            }
        }
    }
    if(arr[G] == 0) cout<<"use the stairs";
    else{
        int cnt = 0;
        for(int i=G;i!=S;i=arr[i]){
            cnt++;
        }
        cout<<cnt;
    }
}
int main(){
    //fill_n(arr,MAX,-1);
    cin>>F>>S>>G>>U>>D;
    bfs();
}

woolim 2년 전 1

pop 할때 방문 안된거만 처리하도록 바꾸줘야 될것 같아요.

14 int now = q.front(); q.pop();

15 if (visited[now]) continue;

else visited[now] = true;

이런식으로 바꿔보세요

daezang102 2년 전 0

@woolim 감사합니다. 해결됐네요.

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

문제

문제

출처

ICPC

메모리 초과 문제입니다.

daezang102 2년 전 0

woolim 2년 전 1

daezang102 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말