[Gold 4] 9019번 DSLR

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

9019번: DSLR

 

이 문제는 BFS를 사용하면 해결할 수 있다.

 

이 문제에서 가장 어려웠던점은 메모리 관리였다.

처음에 queue와 방문 확인을 위한 행렬을 전역 변수로 생성하였다.

이러한 접근은 메모리 초과라는 오류를 발생시켰다.

 

따라서 bfs 함수 내에서 queue를 할당하고 함수가 끝나면 queue를 소멸하게 하여 메모리 초과를 막을 수 있었다.

 

주요 알고리즘은 다음과 같다.

1. 입력 숫자 A와 경로를 queue에 삽입한다.

2. queue의 front를 꺼내고 D, S, L, R에 따라 수를 바꾼다.

3. queue에 D, S, L, R를 경로에 합쳐 삽입한다.

4. 탐색 도중 원하는 값이 queue에서 pop되면 경로를 출력하고 함수를 종료한다.

 

#include <queue>
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int A, B;
int visited[10000] = {0, };

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

    while (!q.empty())
    {
        int now = q.front().first;
        string path = q.front().second;
        q.pop();

        if (now == B)
        {
            cout << path << '\n';
            return;
        }

        int D, S, L, R, temp;
        // D 연산
        D = (now * 2) % 10000;
        if (!visited[D])
        {
            visited[D] = 1;
            q.push(make_pair(D, path + "D"));
        }

        // S 연산
        S = now - 1 < 0 ? 9999 : now - 1;
        if (!visited[S])
        {
            visited[S] = 1;
            q.push(make_pair(S, path + "S"));
        }

        // L 연산
        L = (now % 1000) * 10 + (now / 1000);
        if (!visited[L])
        {
            visited[L] = true;
            q.push(make_pair(L, path + "L"));
        }

        // R 연산
        R = now / 10 + (now % 10) * 1000;
        if (!visited[R])
        {
            visited[R] = 1;
            q.push(make_pair(R, path + "R"));
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    while (T--)
    {
        cin >> A >> B;
        memset(visited, 0, sizeof(visited)); // 초기화
        bfs();
    }

    return 0;
}