글 읽기 - [c++] bfs 메모리 초과 관련 질문입니다.

gi5005 3년 전 0

답은 제대로 나오는것 같은데 메모리 초과때문에 문제가 풀리지않내요 queue안에 vector를 넣은게 문제일까요?

이게 문제라면 빽트레킹을 어떻게 해야할지 모르겠습니다

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include<string.h>
#define MAX 100001
using namespace std;

short dp[1001][1001];

typedef struct DSLR
{
    int Num;
    vector<char> V;
} D;
int main()
{
    int N;
    cin >> N;
    bool vst[10001];
    memset(vst,false,sizeof(vst));
    while (N--)
    {
        int A, B;
        cin >> A >> B;
        queue<D> q;
        vector<char> tmp;
        q.push({A, tmp});

        while (!q.empty())
        {
            pair<int,char> T[4];
            int cur = q.front().Num;
            if(cur == B)
            {
                for(int i=0;i<q.front().V.size();i++)
                {
                    cout << q.front().V[i];
                }
                cout << "\n";
                break;
            }
            T[0].first = (cur * 2) % 10000;
            T[1].first = cur - 1 == 0 ? 9999 : cur - 1;
            T[2].first = (cur % 1000) * 10 + cur / 1000;
            T[3].first = ((cur - cur % 10) / 10) + ((cur % 10) * 1000);
            T[0].second = 'D';
            T[1].second = 'S';
            T[2].second = 'L';
            T[3].second = 'R';
            vector<char> tmpD;
            tmpD = q.front().V;
            q.pop();
            for(int i=0;i<4;i++)
            {
                //cout << T[i] << "\n";
                tmpD.push_back(T[i].second);
                if(!vst[T[i].first])
                {
                    vst[T[i].first]==true;
                    q.push({T[i].first,tmpD});
                }
                tmpD.pop_back();
            }
        }
    }
}

minjoonist 3년 전 0

queue에 vector를 넣으시다니 ㄷㄷ

저는 스택을 이용해서 풀었습니다.

nakgee 3년 전 0

52번째 줄의 문제인 것 같습니다.

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

문제

문제

출처

ICPC

[c++] bfs 메모리 초과 관련 질문입니다.

gi5005 3년 전 0

minjoonist 3년 전 0

nakgee 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말