글 읽기 - C++ bfs 시간초과

hsw0194 3년 전 0

DSLR 문제 푸는데

3%에서 계쏙 시간초과가 나네요..

L과 R연산에서 pow 함수가 오래걸린다길래 미리 계산해놓는 방식으로 했는데도 시간초과가 나네요

무엇이 문제일까요..?

#include <math.h>

#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

#define MAX 10000

int A, B;
vector<char> DSLR_OP(MAX);
vector<bool> visited(MAX);

void ans();

string bfs(queue<pair<int,string>>);

int D(int);

int S(int);

int L(int);

int R(int);

int main(void) {
  int test;
  cin >> test;
  while (test--) {
    cin >> A >> B;
    ans();
  }
}

void ans() {
  queue<pair<int,string>> q;
  q.push(make_pair(A,""));
  visited[A] = true;
  string result = bfs(q);

  cout << result << '\n';

  /* 되돌아가면서 출력
  // stack<char> stack;
  // int tmp=result.first;
  // while (true) {
  //   stack.push(DSLR_OP[tmp]);
  //   switch (DSLR_OP[tmp])
  //   {
  //   case 'D':
  //     tmp/=2;
  //     break;
  //   case 'S':
  //     tmp+=1;
  //     break;
  //   case 'L':
  //     tmp=R(tmp);
  //     break;
  //   case 'R':
  //     tmp=L(tmp);
  //     break;
  //   default:
  //     break;
  //   }
  //   if(tmp==A) break;
  // }

  // // 출력
  // while(!stack.empty()){
  //   cout<<stack.top();
  //   stack.pop();
      }
  */
  for (int i = 0; i < MAX; i++) {
    visited[i] = false;
  }
}

string bfs(queue<pair<int, string>> q) {
  while (!q.empty()) {
    pair<int, string> front = q.front();
    q.pop();

    if (front.first == B) {
      return front.second;
    }

    if (!visited[D(front.first)]) {
      DSLR_OP[D(front.first)] = 'D';
      visited[D(front.first)] = true;
      q.push(make_pair(D(front.first), front.second + 'D'));
    }
    if (!visited[S(front.first)]) {
      DSLR_OP[S(front.first)] = 'S';
      visited[S(front.first)] = true;
      q.push(make_pair(S(front.first), front.second + 'S'));
    }
    if (!visited[L(front.first)]) {
      DSLR_OP[L(front.first)] = 'L';
      visited[L(front.first)] = true;
      q.push(make_pair(L(front.first), front.second + 'L'));
    }
    if (!visited[R(front.first)]) {
      DSLR_OP[R(front.first)] = 'R';
      visited[R(front.first)] = true;
      q.push(make_pair(R(front.first), front.second + 'R'));
    }
  }
  return NULL;
}

int D(int a) { return 2 * a <= 9999 ? 2 * a : (2 * a) % 10000; }

int S(int a) { return a != 0 ? a - 1 : 9999; }

int L(int a) {
  int d[4];
  int pows[4]={1000,100,10,1};
  for (int i = 0; i <= 3; i++) {
    d[i] = a / pows[i];
    a = a - d[i] * pows[i];
  }
  return ((d[1] * 10 + d[2]) * 10 + d[3]) * 10 + d[0];
}

int R(int a) {
  int d[4];
  int pows[4]={1000,100,10,1};
  for (int i = 0; i <= 3; i++) {
    d[i] = a / pows[i];
    a = a - d[i] * pows[i];
  }
  return ((d[3] * 10 + d[0]) * 10 + d[1]) * 10 + d[2];
}

seico75 3년 전 3

L, R를 for없이 구현할 수 있습니다.

(a * 10) % 10000 + a / 1000 이런식으로요.

L, R, D, S 를 4번씩 부르는데 한번 부르고 결과를 재활용하는 것이 시간을 아낄 수 있습니다.

그리고 B에 도달했는지를 큐에서 꺼내면서가 아니라 큐에 넣을때 확인하면 또 시간을 많이 줄일 수 있습니다.

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

문제

문제

출처

ICPC

C++ bfs 시간초과

hsw0194 3년 전 0

seico75 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말