백준 1987 알파벳

알파벳 방문관리를 하며 백트래킹을 수행하면 되는 문제이다.
알파벳은 'A' ~ 'Z'까지 있고 이를 0 ~ 25의 숫자로 대응시킨다.

#include <bits/stdc++.h>
using namespace std;

int r, c;
char board[21][21];
int cnt;
int alpha[26];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void dfs(int k, int x, int y) {
    cnt = max(cnt, k);
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        int idx = board[nx][ny] - 'A';
        if (nx < 1 || nx > r || ny < 1 || ny > c) continue;
        if (alpha[idx]) continue;
        alpha[idx] = 1;
        dfs(k+1, nx, ny);
        alpha[idx] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> r >> c;
    for (int i = 1; i <= r; ++i) {
        for (int j = 1; j <= c; ++j) {
            cin >> board[i][j];
        }
    }
    int idx = board[1][1] - 'A';
    alpha[idx] = 1;
    dfs(1, 1, 1);
    cout << cnt;
}