글 읽기 - bfs 메모리초과 문제가 있습니다!

dowk0331 4년 전 0

bfs 방식을 사용하여 도달 가능한 최대 길이를 출력하는 코드입니다.

어느 방향을 선택하느냐에 따라서 같은 길이에 도달한다해도, 쓰인 알파벳들이 다르기 때문에 check로 알파벳 사용여부를 인자로 넘겨주었습니다만

이부분에서 메모리초과가 나는게 아닌가 조심스럽게 예상이 됩니다.

이부분 때문에 메모리초과가 나는게 맞는지

아니라면 어느 부분때문에 메모리초과가 나는건지 알수 있을까요?

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

struct vertex {
    int row;
    int col;
};
struct info {
    vertex ver;
    int time;
    string chk;
};
int dR[4] = {-1,0,1,0};
int dC[4] = {0,1,0,-1};

int R,C;
vector<string> map;
queue<info> Q;

void input();
void go(info capsule);
int spread();
void output();

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    input();
    output();
    return 0;
}

void input() {
    cin >> R >> C;
    map.assign(R,"");
    for(int i=0; i<R; i++) cin >> map[i];
}
void go(info capsule) {
    for(int i=0; i<4; i++) {
        int newR = capsule.ver.row + dR[i], newC = capsule.ver.col + dC[i];
        if(newR < 0 || newR >= R) continue;
        if(newC < 0 || newC >= C) continue;
        if(capsule.chk[map[newR][newC]-'A'] == '1') continue;
        info newCapsule = capsule;
        newCapsule.chk[map[newR][newC]-'A'] = '1'; // 사용한 알파벳의 index자리는 1로 변경
        newCapsule.ver = {newR,newC};
        newCapsule.time++;
        Q.push(newCapsule);
    }
}
int spread() {
    string check ="00000000000000000000000000"; // 알파벳 사용 여부
    check[map[0][0]-'A'] = '1'; // 사용한 알파벳의 index자리는 1로 변경
    Q.push({{0,0},1,check});
    for(int t=1; ; t++) {
        while(Q.front().time == t) {
            go(Q.front());
            Q.pop();
            if(Q.empty()) return t;
        }
    }
}
void output() {
    cout << spread() << '\n';
}

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

문제

문제

출처

ICPC

bfs 메모리초과 문제가 있습니다!

dowk0331 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말