[BOJ 9019] DSLR (C++)

DSLR (Gold 5)

문제

전체 문제 보기

9019번: DSLR

접근법

이번 문제는 BFS로 풀 수 있지만 상당히 까다로운 문제입니다. 그 이유는 문제를 보고 BFS로 접근해야 한다고 생각하기 어렵고, 최단경로의 경로 크기만 출력하는 것이 아니라 어떤 경로를 지나왔는지까지 출력해야 하기 때문에 고려해야 할 사항이 많습니다. 최단 경로를 기록 및 출력하기 위해서 아래와 같이 현재 값을 만들 수 있는 부모 값 배열 parents와 현재 숫자로 만들기 위해 사용한 연산자 배열 path를 만들어 이동 경로를 기록하였습니다.

이동 경로를 기록할때는 항상 부모 노드밖에 기록할 수 없습니다. 현재 탐색하고 있는 노드가 어떤 노드를 거쳐서 왔는지만 파악할 수 있습니다. 때문에 만약 1234 → 2341 → 3412로 진행되었다면, 3412가 2341을 거쳐서 왔음을 알아도 2341에서 3412로 갔음을 알 수 없습니다. 항상 현재 노드가 복수개의 인접 노드로 탐색을 진행하기 때문입니다. 그래서 탐색이 종료 후 stack을 활용하여 경로를 복원하는 과정까지 구현해야 합니다.

전체 구현

#include <stdio.h>
#include <queue>
#include <array>
#include <stack>
#define endl '\n'
using namespace std;

int Oper_D(int n)
{
    return (n << 1) % 10'000;
}
int Oper_S(int n)
{
    return (n + 9'999) % 10'000;
}
int Oper_L(int n)
{
    return (n * 10) % 10'000 + n / 1'000;
}
int Oper_R(int n)
{
    return (n % 10) * 1'000 + n / 10;
}
array<char, 4> IntToChar{ 'D', 'S', 'L', 'R' };
array<int, 10'000> parents;
array<char, 10'000> path;
void BFS(int start, int target)
{
    parents.fill(-1);
    path.fill('N');
    parents[start] = start;

    queue<int> q;
    q.push(start);

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        // 이동 가능한 경로 계산
        array<int, 4> next{ Oper_D(cur), Oper_S(cur), Oper_L(cur) ,Oper_R(cur) };

        for (int i = 0; i < 4; ++i)
        {
            if (parents[next[i]] == -1)
            {
                parents[next[i]] = cur;
                path[next[i]] = IntToChar[i];
                q.push(next[i]);
                // target 발견시 탐색 종료
                if (next[i] == target) return;
            }
        }
    }
}
void solve()
{
    int A, B; // (A ≠ B),  0 이상 10,000 미만
    scanf("%d %d ", &A, &B);

    BFS(A, B);

    // stack을 활용한 이동경로 복원 및 출력
    stack<char> s;
    int cur = B;
    while(cur != A)
    {
        s.push(path[cur]);
        cur = parents[cur];
    }
    while (!s.empty())
    {
        printf("%c", s.top());
        s.pop();
    }
    printf("\n");
}
int main() {
    int T; // 테스트 케이스
    scanf("%d ", &T);

    while (T--)
    {
        solve();
    }

    return 0;
}