글 읽기 - 메모리초과가 나는데요. 돠주세요 ㅠ 흙흙

plzrun 8년 전 0

queue에 너무 많이 들어가서 메모리초과가 나는거 같은데 도와주세요 ㅠㅠ

아예 다른 방법으로 접근해야 할까요??

아 그리고 만약 문자판이 B A B A B이고 k값이 5일때 BAB란 문자열이 몇개있는지 보면 (밑에 인덱스만 기재해볼게요)

121, 123, 125, 141, 143, 145, 321, 323, 343, 341, 345, ...

ㄷㄷㄷㄷㄷㄷㄷ 다 쓰려고 했는데 너무 많네요.

아무튼 저걸 의미하는거 맞나요? 아니면 각각의 경로에서 한번 지나온 곳은 다시 가면 안되나요? 예를들면 위에서 121, 323, 343 같은게 안되냐는 질문입니다.

#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;
char str[81], v[100][101];
struct Plate{
    signed char x, y;
    Plate(signed char xx, signed char yy) {
        x=xx; y=yy;
    }
};
queue<Plate> q;
int main() {
    signed char n, m, k;
    scanf("%hhd %hhd %hhd", &n, &m, &k);
    for(int i=0; i<n; i++) {
        scanf("%s", v[i]);
    }
    scanf("%s", str);
    int len = strlen(str);
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(str[0] == v[i][j]) {
                q.push(Plate(i,j));
            }
        }
    }
    int cnt = 0, idx=1;
    Plate p(0,0);
    while(!q.empty()) {
        int sz = q.size();
        for(int t=0; t<sz; t++) {
            p = q.front(); q.pop();
            if(idx == len) cnt++;
            else {
                for(int i=1; i<=k; i++) {
                    signed char nx = p.x-i;
                    signed char px = p.x+i;
                    signed char ny = p.y-i;
                    signed char py = p.y+i;
                    if(nx >= 0) {
                        if(str[idx] == v[nx][p.y]) {
                            q.push(Plate(nx,p.y));
                        }
                    }
                    if(px < n) {
                        if(str[idx] == v[px][p.y]) {
                            q.push(Plate(px,p.y));
                        }
                    }
                    if(ny >=0) {
                        if(str[idx] == v[p.x][ny]) {
                            q.push(Plate(p.x,ny));
                        }
                    }
                    if(py < m) {
                        if(str[idx] == v[p.x][py]) {
                            q.push(Plate(p.x,py));
                        }
                    }
                }
            }
        }idx++;
    }
    printf("%d", cnt);
    return 0;
}

plzrun 8년 전 2

저렇게 풀면 안된다고 하더군요.. bfs로 하면 메모리초과가 날수밖에 없다고해서

dfs로 바꿨구요. memoization활용해서 해결했습니다.

오렌지님과 유카리코님 알고고고님이 도움주셔서 풀 수 있었습니다. 감사합니다. ㅎ

vjerksen 6년 전 0

아주 기초적인 질문일 수 있는데...

제 생각엔 BFS로 문제를 해결할 때, 큐에 많은 정보들이 담겨서 메모리 초과가 발생한다고 생각됩니다.

근데 이게 정확한 계산 없이 막연한 생각인데.. 메모리 초과가 발생하는 예시와 과정을 알 수 있을까요?

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

문제

문제

출처

ICPC

메모리초과가 나는데요. 돠주세요 ㅠ 흙흙

plzrun 8년 전 0

plzrun 8년 전 2

vjerksen 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말