[BOJ][C#] 1987 알파벳

📕 문제

📌 링크

📗 접근 방식

상하좌우를 돌며 알파벳의 사용 여부를 기록하고 DFS 진입하며 DFS 탈출 시 알파벳의 사용 여부를 복구하는 백트래킹 방식을 생각하였다.
상하좌우를 돌며 범위를 벗어나는지 확인하고 현재 알파벳을 사용 여부를 판단하여 다음 DFS를 진입할 것인지 돌아갈 것인지 작성하였다.
최대값만 알면 되기에 DFS 진입할 때마다 answer을 최신화 시켜주었다.

📘 코드

namespace BOJ
{
    class No_1987
    {
        static int R, C;
        static char[,] arr;
        static int[,] board;
        static bool[] used = new bool[26];
        static int answer = 0;
        static int[] dx = new int[] { 1, 0, -1, 0 };
        static int[] dy = new int[] { 0, 1, 0, -1 };

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

            int[] inputs = Array.ConvertAll(input.ReadLine().Split(), int.Parse);

            R = inputs[0];
            C = inputs[1];

            arr = new char[R, C];
            board = new int[R, C];

            for(int i=0 ;i<R; i++)
            {
                var s = input.ReadLine().ToCharArray();

                for(int j=0 ;j<C; j++)
                    arr[i,j] = s[j];
            }

            used[arr[0, 0] - 'A'] = true;
            DFS(0, 0, 1);

            output.WriteLine(answer);
        }

        static void DFS(int x, int y, int count)
        {
            answer = Math.Max(answer, count);

            for(int dir=0 ;dir<4 ;dir++)
            {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if(nx >= 0 && ny >= 0 && nx < R && ny < C)
                {
                    if(!used[arr[nx, ny] - 'A'])
                    {
                        used[arr[nx, ny] - 'A'] = true;
                        DFS(nx, ny, count + 1);
                        used[arr[nx, ny] - 'A'] = false;
                    }
                }
            }
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 백트래킹