백준 9019번 문제 ( DSLR )

문제 출처 : https://www.acmicpc.net/problem/9019

9019번: DSLR

이번 문제는 BFS를 이용하여 해결하는 문제이다.

기본적인 BFS 기법을 이용하여 해결하는 문제이지만 구조체에 char 배열을 선언해서 저장하는 형식으로 

풀어보았더니 타임 에러가 나오게 되었다.

그리고 숫자가 -1 될 때 0 일때 9999가 되는 것이 아니고 -1 일때 9999가 되는 것이므로 

런타임 에러도 조심해야 한다. 

그래서 check 배열로 타고 가는 것을 역추적하는 방식으로 타임 에러를 해결 할 수 있었다.

아래는 해당 문제를 풀이한 소스 코드이다.

#include<stdio.h>
#include<queue>
#pragma warning(disable:4996)
using namespace std;
int start, finish;
int visit[10001];
int check[10001];
int dir[10001];
char arr[10001];
struct list
{
    int num;
    int cnt = 0;
};
queue <list> que;
// D 2배 S n-1 L 왼편으로 이동 R 우측으로 이동
int D(int num)
{
    int n = 2 * num;
    if (n > 9999)
        n = n % 10000;
    return n;
}
int S(int num)
{
    int n = num - 1;
    if (n == -1)
        n = 9999;
    return n;
}
int L(int num)
{
    int n = num / 1000;
    int temp = (num % 1000) * 10;
    return temp+n;
}
int R(int num)
{
    int n = num % 10;
    int temp = num / 10;
    return 1000 * n + temp;
}
void BFS()
{
    while (!que.empty())
    {
        list temp = que.front();
        que.pop();
        int num;
        if (temp.num == finish)
        {
            int i = 0;
            int x = finish;
            while (1)
            {
                if (x == start)
                    break;
                if (dir[x] == 1)
                    arr[i] = 'D';
                else if (dir[x] == 2)
                    arr[i] = 'S';
                else if (dir[x] == 3)
                    arr[i] = 'L';
                else
                    arr[i] = 'R';
                x = check[x];
                i++;
            }
            for (int i = temp.cnt - 1; i >= 0; i--)
            {
                printf("%c", arr[i]);
            }
            printf("\n");
            return;
        }
        list A = temp;
        num = D(temp.num);
        if (visit[num] == 0)
        {
            visit[num]=1;
            check[num] = temp.num;
            dir[num] = 1;
            A.num = num;
            A.cnt = temp.cnt + 1;
            que.push(A);
        }
        num = S(temp.num);
        if (visit[num] == 0)
        {
            visit[num]=1;
            A.cnt = temp.cnt + 1;
            check[num] = temp.num;
            dir[num] = 2;
            A.num = num;
            que.push(A);
        }
        num = L(temp.num);
        if (visit[num] == 0)
        {
            check[num] = temp.num;
            dir[num] = 3;
            visit[num]=1;
            A.cnt = temp.cnt + 1;
            A.num = num;
            que.push(A);
        }
        num = R(temp.num);
        if (visit[num] == 0)
        {
            check[num] = temp.num;
            dir[num] = 4;
            visit[num]=1;
            A.cnt = temp.cnt + 1;
            A.num = num;
            que.push(A);
        }
    }
}
void reset()
{
    for (int i = 0; i <= 10000; i++)
        visit[i] = 0;
    while (!que.empty())
        que.pop();
}
int main()
{
    int Test;
    scanf("%d", &Test);
    for (int i = 0; i < Test; i++)
    {
        scanf("%d %d", &start, &finish);
        list temp;
        temp.num = start;
        visit[start] = 1;
        que.push(temp);
        BFS();
        reset();
    }
}