[백준] 1987. 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력

2 4
CAAB
ADCB

예제 출력

3

풀이

/* Date: 2020-09-30 */
#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

int R, C, Rst = 0;
char Map[21][21];
bool check[91];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void init(){
    cin >> R >> C;
    string s;
    for(int r = 1; r <= R; r++){
        cin >> s;
        for(int c = 0; c < C; c++){
            Map[r][c + 1] = s[c];
        }
    }
}

void dfs(int x, int y, int cnt){
    check[Map[x][y]] = 1; 
    for(int i = 0; i < 4; i++){
        if(is_visitable(x + dx[i], y + dy[i], Map[x + dx[i]][y + dy[i]])){
            dfs(x + dx[i], y + dy[i], cnt + 1);
        }
    }
    check[Map[x][y]] = 0;
    if(Rst < cnt) Rst = cnt;
}

int is_visitable(int x, int y, char next){
    if(x >= 1 && x <= R && y >= 1 && y <= C && !check[next]) return true;
    return false;
}

int main(){
    init();
    dfs(1, 1, 1);
    cout << Rst << endl;
}

알파벳 중복 확인을 위해 벡터를 사용했더니 시간이 어마어마하게 걸렸다.(멍청ㅠ)
알파벳 A~Z의 아스키코드 값은 대문자는 65~90, 소문자는 97~122 이다.
크기가 91인 (대문자 Z까지 중복체크를 해야 하므로) 배열을 만들어 중복 확인을 함으로써 시간 초과 문제를 해결했다.