글 읽기 - cpp 시간초과 질문입니다

adxx 3년 전 0

안녕하세요 TLE를 받는데 미스난 부분이 어딘지 짐잣이 되지 않아 질문드립니다

현재 숫자의 상태를 정점으로 DSLR 연산을 간선으로 보고 BFS를 통해 문제를 해결하는 중 이고

이에따른 시간 복잡도는 O(NlogN) 정도라고 생각합니다(이때 N은 가능한 숫자가 약 1만개임으로 이와 같다 생각됩니다)

이때 뒤에 로그하나가 따라오는 이유는 숫자의 상태를 정점으로 볼 때, map을 이용하여 이를 확인하기에 map의 삽입, 검색의 시간복잡도가 붙은 것 입니다

mp[i] := 현재 숫자가 i일때 이 정점의 번호

par[I] := 정점 i에서의 부모 노드

출력문은 도착한 정점까지의 부모노드를 돌면서 한글자씩 모으고 이를 다시 뒤집어서 출력합니다

긴 글 읽어주셔서 감사합니다🙂

P.S.

특별히 중복 방문이나, queue에서 pop을 하지 않는 등의 문제는 눈에 띄지 않습니다

#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"
#include "map"

using namespace std;
bool vis[10000];
string dist[10000];
int par[10000];
map<int, int> mp; // 숫자, 인덱스
int ori,dest;

bool check(int a, int b) {
    if (a==b) return true;
    return false;
}

string bfs(int a) {
    vector<int> origin;
    int idx = 0;
    queue<tuple<int, int>> que; // 만들어진 숫자, idx
    mp[a]=0;
    vis[0]=true;
    que.push({a, 0});
    dist[0]="";
    par[0]=0;
    while (!que.empty()) {
        tuple<int, int> cur = que.front();que.pop();
        int nowIdx = get<1>(cur);
        int nowNum = get<0>(cur);
        // D
        int d = nowNum;
        d*=2;
        if (d>9999) d%=10000;
        if (mp.find(d) == mp.end()) {
            mp[d]=++idx;
            vis[idx]=true;
            dist[idx]= "D";
            par[idx]=nowIdx;
            que.push({d, idx});
        }
        if (check(d, dest)) {
            return dist[idx];
        }
        // S
        int s = nowNum;
        s--;
        if (s==-1) s=9999;
        if (mp.find(s) == mp.end()) {
            mp[s]=++idx;
            vis[idx]=true;
            dist[idx]= "S";
            par[idx]=nowIdx;
            que.push({s, idx});
        }
        if (check(s, dest)) {
            return dist[idx];
        }
        // L
        int l = (nowNum%1000)*10+nowNum/1000;
        if (mp.find(l) == mp.end()) {
            mp[l]=++idx;
            vis[idx]=true;
            dist[idx]= "L";
            par[idx]=nowIdx;
            que.push({l, idx});
        }
        if (check(l, dest)) {
            return dist[idx];
        }
        // R
        int r = (nowNum%10)*1000+nowNum/10;
        if (mp.find(r) == mp.end()) {
            mp[r]=++idx;
            vis[idx]=true;
            dist[idx]= "R";
            par[idx]=nowIdx;
            que.push({r, idx});
        }
        if (check(r, dest)) {
            return dist[idx];
        }

    }
    return "";
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int tc;
    cin >> tc;
    while (tc--) {
        mp.clear();
        fill(vis, vis+10000, false);
        fill(dist, dist+10000, "");
        cin >> ori >> dest;
        bfs(ori);
        auto it = mp.find(dest);
        int idx = it->second;
        string ans = "";
        for (int i = idx;i!=0; i=par[i]) {
            ans+=dist[i];
        }
        reverse(ans.begin(), ans.end());
        cout << ans << "\n";
    }
    return 0;
}

adxx 3년 전 0

문제를 다시 풀고 난 이후(AC 받음) 위의 코드를 보고 드는 생각은 TLE가 당연하다는 겁니다

한번의 방문마다 4번의 mp.find 호출이 발생하는데 정확히 계산을 해보지는 않았지만 지수함수꼴의 시간복잡도로 보입니다

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

문제

문제

출처

ICPC

cpp 시간초과 질문입니다

adxx 3년 전 0

adxx 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말