[BOJ] 백준 1987 알파벳

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

 Input 

2 4

CAAB

ADCB

　 

 Output 

3

서로 다른 알파벳으로 이루어진 최대 경로

같은 알파벳이 적힌 칸을 두 번 지나갈 수 없는 조건을 확인하기 위해 

visited[26]을 사용하지 않고 비트마스크 활용

ex) 0 00000 00000 00000 00000 00011 → BA

ex) 1 00000 00000 00000 00000 00101 → ZCA

---

#include <iostream>
using namespace std;
#define MAX 20
 
int R, C, answer;
string board[MAX];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void DFS(int x, int y, long long alphabet, int cnt){
 
    // 현재 알파벳 표시 (비트마스크)
    alphabet |= (1 << (board[x][y] - 'A')); 
 
    for (int i = 0; i < 4; i++){
        int nextX = x + dx[i];
        int nextY = y + dy[i];
        
        if(nextX < 0 || nextX >= R || nextY < 0 || nextY >= C)
            continue;
        
        // 이미 지나온 알파벳인 경우
        if (alphabet & (1 << (board[nextX][nextY] - 'A')))
            continue;
        
        DFS(nextX, nextY, alphabet, cnt + 1);
    }
    answer = answer < cnt ? cnt : answer;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        cin >> board[i];
    
    answer = -1;
    DFS(0, 0, (long long)1 << 26, 1); //알파벳 A(0) ~ Z(25)
    cout << answer << endl;
}