1987번 - 알파벳

https://www.acmicpc.net/problem/1987

1987번: 알파벳

#include <iostream>
using namespace std;
int R, C, ans = 0;
char board[21][21];
bool check[26] = {false};
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
bool isPossible(int row, int col)
{
    if(row<0 || row >= R || col<0 || col>=C)
        return false;
    return true;
}
void dfs(int row, int col, int cnt)
{
    //ans update
    if(ans < cnt)
        ans = cnt;

    for(int i=0; i<4; i++)
    {
        int ny = row + dy[i];
        int nx = col + dx[i];
        if(true == isPossible(ny,nx) && false == check[board[ny][nx]-65])
        {
            int idx = board[ny][nx] - 65;
            check[idx] = true;
            dfs(ny, nx, cnt+1);
            check[idx] = false; //backtracking
        }
        
    }
}
int main()
{
    cin >> R >> C;

    char tmp;
    for(int i=0; i<R; i++)
    {
        for(int j=0; j<C; j++)
        {
            cin >> tmp;
            board[i][j] = tmp;
        }
    }

    check[board[0][0]-65] = true; //첫번째 값 표시
    dfs(0, 0, 1); //dfs 실행

    cout << ans << '\n';
    return 0;
}