[BOJ][C#] 1909 DSLR

📕 문제

📌 링크

📗 접근 방식

BFS 을 이용하여 구현하였다.
bool배열 대신하여 HashSet을 이용해 중복처리

📘 코드

namespace BOJ
{
    class No_1909
    {
        static HashSet<int> visited = new HashSet<int>();
        static Queue<(int, string)> q = new Queue<(int, string)>();

        static void Main()
        {
            int testCase = int.Parse(Console.ReadLine());

            while(testCase-->0)
            {
                int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int start = inputs[0];
                int target = inputs[1];

                string answer = BFS(start, target);
                Console.WriteLine(answer);
            }
        }

        static string BFS(int A, int B)
        {
            visited.Clear();
            q.Clear();

            q.Enqueue((A, ""));

            while(q.Count > 0)
            {
                var cur = q.Dequeue();
                int curNum = cur.Item1;
                string curString = cur.Item2;

                if(curNum == B) return curString;
                

                if(!visited.Contains(curNum))
                {
                    visited.Add(curNum);
                    q.Enqueue((D(curNum), curString + "D"));
                    q.Enqueue((S(curNum), curString + "S"));
                    q.Enqueue((L(curNum), curString + "L"));
                    q.Enqueue((R(curNum), curString + "R"));
                }
            }

            return "";
        }

        static int D(int n) => (2 * n) % 10000;
        static int S(int n) => (n - 1 + 10000) % 10000;
        static int L(int n) => (n * 10) % 10000 + n / 1000;
        static int R(int n) => n / 10 + (n % 10) * 1000;
    }
}

📙 오답노트

1. DFS 접근 (Overflow)
   처음에 DFS로 풀려고 구현하고 풀어보니 stack overflow가 났다.
   아마 BFS처럼 최단을 탐색하는 것이 아니라 깊이 우선이다 보니 depth를 걸어서 return해주었지만 overflow가 난 것 같다.

   해결 방법
   알고리즘을 보아하니 DFS가 없어 BFS로 접근방식을 바꾸었다..

2. BFS 접근 (메모리 초과)
   BFS함수 시작시 Queue와 HashSet을 new 해서 생성시켜줬는데
   반복문 내부에서 Object 생성 시, GC가 이것을 제때 처리 해 주지 않는 것 같습니다.

   해결 방법
   상단에 접근할 수 있게 static 키워드를 사용하여 선언해준 후 BFS함수 진입 시, Queue와 HashSet을 Clear() 시켜주었다.
   

📒 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색