[BOJ][C#] 12919 A와 B 2

📕 문제

📌 링크

📘 코드

DFS 방식

namespace BOJ
{
    class No_12919
    {
        static bool canChange = false;

        static void Main()
        {
            using StreamReader input = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter output = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            string start = input.ReadLine();
            string end = input.ReadLine();

            DFS(start, end);

            if(canChange)
                output.WriteLine(1);
            else
                output.WriteLine(0);
        }

        static void DFS(string start, string end)
        {
            if(canChange)
                return;

            if(start.Length == end.Length)
            {
                if(start == end)
                    canChange = true;
                else
                    canChange = false;

                return;
            }

            if(end[end.Length-1] == 'A')
                DFS(start, PopBack(end));

            char[] chars = end.ToCharArray();
            Array.Reverse(chars);
            end = new string(chars);

            if(end[end.Length - 1] == 'B')
                DFS(start, PopBack(end));
        }

        static string PopBack(string s)
        {
            return s.Substring(0, s.Length - 1);
        }
    }
}

BFS 방식

namespace BOJ
{
    class No_12919
    {
        static bool canChange = false;

        static void Main()
        {
            using StreamReader input = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter output = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

            string start = input.ReadLine();
            string end = input.ReadLine();

            Queue<string> q = new Queue<string>();

            q.Enqueue(end);

            while(q.Count > 0)
            {
                string cur = q.Dequeue();

                if(cur.Length <= 0)
                    continue;

                if(cur == start)
                {
                    canChange = true;
                    break;
                }

                if(cur[cur.Length - 1] == 'A')
                {
                    string s1 = cur.Substring(0, cur.Length - 1);
                    if(!q.Contains(s1))
                        q.Enqueue(s1);
                }

                char[] chars = cur.ToCharArray();
                Array.Reverse(chars);
                cur = new string(chars);

                if(cur[cur.Length - 1] == 'B')
                {
                    string s2 = cur.Substring(0, cur.Length - 1);
                    if(!q.Contains(s2))
                        q.Enqueue(s2);
                }
            }

            if(canChange)
                output.WriteLine(1);
            else
                output.WriteLine(0);
        }
    }
}

📙 오답노트

처음에는 start 문자열을 수정하여 end 문자열과 같은지 판단하는 로직으로 재귀를 구현하였다.
하지만 이 로직은 시간초과였고 질문하기를 통해 start 문자열을 수정하는 것이 아니라 end 문자열을 수정하여 start 문자열과 같은지 판단하는 로직을 구현한 분을 확인한 후 수정하였더니 정답이였다.

또한 저는 DFS방식으로 해결하였지만 질문하기에서는 BFS로 해결한 것을 보고 BFS로도 문제 제출을 해보았다.

📒 알고리즘 분류

• 문자열
• 브루트포스 알고리즘
• 재귀