[Algorithm] Baekjoon 9019번 : DSLR

https://www.acmicpc.net/problem/9019

9019번: DSLR

struct Node
{
    int num;
    string operations;
};
 
bool visited[10001] = { false };
 
string BFS(int start, int target)
{
    queue<Node> q;
    q.push({ start,"" });
    string answer = "";
    visited[start] = true;
 
    while (!q.empty())
    {
        Node curNode = q.front();
        q.pop();
 
        int curNum = curNode.num;
        string curOperations = curNode.operations;
 
        if (curNum == target)
        {
            answer = curOperations;
            break;
        }
 
        int D = (curNum * 2) % 10000;
        int S = curNum == 0 ? 9999 : curNum - 1;
        int L = curNum / 1000 + (curNum % 1000) * 10; 
        int R = curNum / 10 + (curNum % 10) * 1000;
 
        if (!visited[D])
        {
            visited[D] = true;
            q.push({ D,curOperations + "D" });
        }
 
        if (!visited[S])
        {
            visited[S] = true;
            q.push({ S,curOperations + "S"});
        }
 
        if (!visited[L])
        {
            visited[L] = true;
            q.push({ L,curOperations + "L"});
        }
 
        if (!visited[R])
        {
            visited[R] = true;
            q.push({ R,curOperations + "R"});
        }
    }
 
    return answer;
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    vector<string> results;
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        memset(visited, false, sizeof(visited));
        int a, b;
        cin >> a >> b;
        results.push_back(BFS(a, b));
    }
 
    for (auto& temp : results)
    {
        cout << temp << endl;
    }
}

 

해결하고나서 배운게 있는 문제.

D와 S는 그대로 구현하면 되는데, L과 R은 처음에 풀 때 편하게 String으로 변환했었다.

애초에 입력을 string으로 받고 L은 입력 문자열의 L = S.substr(1,3) + S[0]; 
이런식으로..

그러다보니 코드에 to_string이라던가 stoi 등등, 변환하는 함수들도 많이 쓰여지고 하다보니 시간초과가 떴다.

그래서 전부 지우고 string을 사용하지않고 코드를 다시 짰더니 통과했다.

 

이런부분에 대한 시간초과는 신경쓴적 없었는데 덕분에 이제는 조심하게 될 것 같다.