[BOJ] 1987번: 알파벳

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

예전에 풀었는데 놀랍게도 풀이를 적지 않았나 보다..

DFS에 백트래킹을 섞어주면 된다.

#include <cstdio>
 
char board[21][21];
bool al[26];
int R, C, count = -987654321;
 
const int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };
 
bool is_safe(int y, int x) {
    return (0 <= y && y < R && 0 <= x && x < C);
}
 
void search(int y, int x, int cnt) {
    if (cnt > count) count = cnt;
    al[board[y][x] - 'A'] = true;
    for (int i = 0; i < 4; ++i) {
        int nextY = y + dy[i], nextX = x + dx[i];
        if (is_safe(nextY, nextX) && !al[board[nextY][nextX] - 'A'])
            search(nextY, nextX, cnt + 1);
    }
    al[board[y][x] - 'A'] = false;
}
 
int main()
{
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; ++i) scanf("%s", board[i]);
    search(0, 0, 1);
    printf("%d\n", count);
    return 0;
}