이번 문제는 그래프 탐색, 백트레킹, DFS를 통해 해결할 수 있는 문제였다.

• 보드의 입력이 문자열로 이뤄지므로 string으로 받아 배열에 저장하였다.
• bool형 배열을 통해 지난 알파벳인지 판별한다.
• 상하좌우로 밟지 않은 칸으로 이동하며 밟은 표시를 해주며 진행하고, 밟지 않은 칸으로 바꿔준 뒤에 다른 경로에 대해 탐색해준다. (가능한 모든 경로를 탐색하기 위해)
• DFS로 모든 경로를 탐색해준다.

Code

#include <iostream>
#include <string>
#define MAX 21
using namespace std;

int r,c;
string road;
char field[MAX][MAX];
bool visited[26];
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
int result=1;

int Big(int a, int b){
    if(a>b)
        return a;
    return b;
}

void Input(){
    cin>>r>>c;
    for(int i=0; i<r; i++){
        cin>>road;
        for(int j=0; j<c; j++){
            field[i][j]=road[j];
        }
    }
}

void DFS(int y, int x, int cnt){
    result=Big(result, cnt);
    for(int i=0; i<4; i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny>=0&&nx>=0&&ny<r&&nx<c){
            if(!visited[field[ny][nx]-'A']){
                visited[field[ny][nx]-'A']=true;
                DFS(ny, nx, cnt+1);
                visited[field[ny][nx]-'A']=false;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    visited[field[0][0]-'A']=true;
    DFS(0,0,1);
    cout<<result<<endl;
    return 0;
}