글 읽기 - 소스에 어떤 부분이 시간적으로 비효율적인지 모르겠습니다. 도와주세요!

mhccc 5년 전 0

우선 정답을 받아내긴 했는데 실행 시간이 오래걸려서 좋은 답은 아닌 것 같아 질문 올립니다.

제 코드에서 어떤 부분이 시간을 많이 잡아먹고 있는 것인가요?? 도움 부탁드립니다. 감사합니다 (_ _)

//
//  main.cpp
//  ProblemSolving
//
//  Created by MINHYUKCHO..
//  Copyright © 2018년 MINHYUKCHO. All rights reserved.
//

#include <iostream>
#include <queue>
using namespace std;
pair<bool, string> c[10000];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        for(int i=0; i<10000; i++) {
            c[i].first = false;
            c[i].second = "";
        }
        int a, b;
        cin >> a >> b;
        queue<int> q;
        q.push(a);
        c[a].first = true;
        while(!q.empty()) {
            int cur = q.front();
            if(cur == b) {
                break;
            }
            int next;
            string path;
            next = (cur*2) % 10000;
            path = c[cur].second;
            if(c[next].first == false) {
                q.push(next);
                c[next].first = true;
                c[next].second = path.append("D");
            }
            next = (cur==0) ? 9999 : cur-1;
            path = c[cur].second;
            if(c[next].first == false) {
                q.push(next);
                c[next].first = true;
                c[next].second = path.append("S");
            }
            next = (cur%1000)*10 + cur/1000;;
            path = c[cur].second;
            if(c[next].first == false) {
                q.push(next);
                c[next].first = true;
                c[next].second = path.append("L");
            }
            next = (cur%10)*1000 + cur/10;
            path = c[cur].second;
            if(c[next].first == false) {
                q.push(next);
                c[next].first = true;
                c[next].second = path.append("R");
            }
            q.pop();
        }
        cout << c[b].second << "\n";
    }
    return 0;
}

djm03178 5년 전 2

BFS로 한 단계 나아갈 때마다 기존의 path를 받아서 이어붙이면 그 길이에 비례하는 시간이 매번 걸려서 비효율적입니다. string을 만들고 지우는 것 자체가 꽤 무거운 연산이기도 합니다.

BFS의 경로를 추적할 때 완성품을 보내주지 말고, 이전 상태가 어디였고 거기서 무슨 연산을 한 건지만 알려주면 BFS가 끝난 후에 경로를 역추적해서 재구성을 할 수 있습니다. string 대신에 char을 쓸 수 있어서 더 가볍습니다.

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

문제

문제

출처

ICPC

소스에 어떤 부분이 시간적으로 비효율적인지 모르겠습니다. 도와주세요!

mhccc 5년 전 0

djm03178 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말