[BOJ/백준] 1987 - 알파벳

1987번: 알파벳

---

---

---

• 제목

알파벳

---

• 조건

시간 제한 : 2 초

메모리 제한 : 256 MB 

---

• 문제

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

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

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

---

• 입력

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

---

• 출력

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

---

예제 입력1	예제 출력1
2 4 CAAB ADCB	3

예제 입력2	예제 출력2
3 6 HFDFFB AJHGDH DGAGEH	6

예제 입력3	예제 출력3
5 5 IEFCJ FHFKC FFALF HFGCF HMCHH	10

---

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
char map[20][20];
int N, M, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}, depth[20][20], ans = 1;
bool visited[20][20], alphabet[26];
void DFS(int row, int column){
    visited[row][column] = true;
    alphabet[map[row][column] - 'A'] = true;
    for(int n = 0 ; n < 4 ; n++){
        int r = dx[n] + row;
        int c = dy[n] + column;
        if(r >= 0 && r < N && c >= 0 && c < M && !visited[r][c] && !alphabet[map[r][c] - 'A']) { 
            depth[r][c] = depth[row][column] + 1;
            ans = max(ans, depth[r][c]);
            DFS(r, c);
        }
    }
    visited[row][column] = false;
    alphabet[map[row][column] - 'A'] = false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    for(int n = 0 ; n < N ; n++) for(int m = 0 ; m < M ; m++) depth[n][m] = 1;
    for(int n = 0 ; n < N ; n++){
        cin.ignore();
        for(int m = 0 ; m < M ; m++) cin >> map[n][m];
    }
    for(int n = 0 ; n < 26 ; n++) alphabet[n] = false;
    DFS(0, 0);
    cout << ans << endl;
    return 0;
}