백준 C# 9019 DSLR

문제

입력되는 DSLR 명령을 통해 입력 숫자와 결과 숫자를 같게 만들기 위해 몇번의 명령이 최소한으로 필요한 것인지 판단

물론 같은 순서로 같은 결과값이 나오는 경우가 있겠지만, 그것은 고려하지 않는 듯

 

해결

모든 경우의 수를 고려해야 되는 것이기 때문에 하나의 진행사항이 진행된 후 다른 진행 사항도 동시에 진행을 해야되는 것이 문제였다.
각 경우를 모두 문어발과 같이 퍼저나가는 것을 만드는 것이 목적이다.

 

방문을 판단하는 까닭 : LR 같은 명령은 4번이 진행된 후 반복되기 때문

기록하는 방법이 실패한 이유 : Stack.Contain으로 방문을 판단했는데, 탐색하는 시간 때문에 시간 초과가 발생

 

using System.Collections.Generic;
using System;
using System.Linq;
using System.IO;
using System.Text;

namespace ConsoleApp1
{
    struct info{
        public int num;
        public string mandate;
    }
    internal class TEST
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
            {
                int iter = int.Parse(sr.ReadLine());
                for (int i = 0; i < iter; i++)
                {
                    int[] v = sr.ReadLine().Split().Select(int.Parse).ToArray();

                    Queue<info> q = new Queue<info>();
                    q.Enqueue(new info { num = v[0], mandate = "" });
                    bool[] register = new bool[10000];

                    while (true)
                    {
                        var a = q.Dequeue();
                        if (a.num == v[1])
                        {
                            sb.AppendLine(a.mandate);
                            break;
                        }

                        //D
                        int D = a.num * 2 % 10000;
                        if (!register[D])
                        {
                            register[D] = true;
                            q.Enqueue(new info { num = D, mandate = $"{a.mandate}D" });
                        }
                        //S
                        int S = (a.num - 1 + 10000) % 10000;
                        if (!register[S])
                        {
                            register[S] = true;
                            q.Enqueue(new info { num = S, mandate = $"{a.mandate}S" });
                        }
                        //L
                        int L = a.num % 1000 * 10 + a.num / 1000;
                        if (!register[L])
                        {
                            register[L] = true;
                            q.Enqueue(new info { num = L, mandate = $"{a.mandate}L" });
                        }
                        //R
                        int R = a.num / 10 + a.num % 10 * 1000;
                        if (!register[R])
                        {
                            register[R] = true;
                            q.Enqueue(new info { num = R, mandate = $"{a.mandate}R" });
                        }
                    }
                }
            }
            Console.WriteLine(sb);
        }
    }
}