백준 - 1987번 : 알파벳 (C++)

풀이 방법 : 백 트래킹

해당 알파벳을 지났는지 체크해서 step수를 늘려가다가 이미 지났던 알파벳을 만나면 최댓값을 갱신 시켜주면 된다.
시작지점인 좌상단을 포함하라고 했으니 시작 Step을 1로 넣어준다.

#include <iostream>
#include <cmath>
#include <limits.h>

using namespace std;

int R, C;
bool Check[27] = {};
char Board[21][21] = {};

int DirY[4] = { 0,0,1,-1 };
int DirX[4] = { 1,-1,0,0 };

int Max = 1;

void DFS(int CurY, int CurX, int Cnt)
{
    Max = max(Cnt, Max);
    for (int i = 0; i < 4; ++i)
    {
        int NextY = CurY + DirY[i];
        int NextX = CurX + DirX[i];

        bool IsOut = NextY < 0 || NextY >= R || NextX < 0 || NextX >= C;

        if (IsOut)
            continue;

        char CurCharacter = Board[NextY][NextX];
        int Idx = (int)CurCharacter - (int)'A';
           
        if (Check[Idx])
            continue;

        Check[Idx] = true;
        DFS(NextY, NextX, Cnt + 1);
        Check[Idx] = false;
    }
}

int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> R >> C;

    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            cin >> Board[i][j];

    char CurCharacter = Board[0][0];
    int Idx = (int)CurCharacter - (int)'A';
    
    Check[Idx] = true;
    DFS(0, 0, 1);
    Check[Idx] = false;

    cout << Max;

}