백준 1987번 - 알파벳

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

이미 방문하여 검사한 부분은 확인하지 않고 
인접한 방향으로 최대한 얼마만큼 갈 수 있는지에 대한 문제이다. 


처음에 한 번이라도 방문했는지에 대한 검사를 수행할 때
보드에서 해당 좌표를 visited로 체크 했는지 검사 했다.
그런데 보드의 좌표를 검사하지 않아도 해당 알파벳을 이전에 방문했는지만 알면 된다.




즉, 이전에 방문하지 않은 지점이 있다고 하더라도 그 지점이 이전에 방문한 지점의 알파벳과 같다면 방문할 수 없다. 

포인트는 방문한 위치가 아니라 방문한 지점의 알파벳이다.



예를 들어 이전에 방문한 지점의 알파벳인 'A'를 visited로 확인했다면, 

visited로 체크된 'A'알파벳이 있는 지점은 (이전에 이 지점을 방문했든 안 했든) 갈 수가 없는 곳이다. 

굳이 이전에 방문한 부분의 좌표를 검사하지 않아도 된다. 

어차피 'A'가 있는 모든 부분은 갈 수가 없기 때문이다.




알파벳이 'A'부터 'Z'까지 주어지는데
문자를 int형으로 변환하면 10진수로 각각 65와 90의 값이다.
'A'의 경우 int로 형 변환 한 다음에 65를 빼준 값인 "0"을 위치로 설정하고 
'Z'는 배열의 25번째 위치로 설정했다.



그리고 dfs 함수를 호출하기 전에 방문한 지점의 알파벳을 방문한 것으로 체크하고
dfs를 호출한 다음에는 좀 전에 방문한 지점의 알파벳을 방문하지 않은 것으로 체크했다.
(다른 경로로 가는 경우도 모두 구하기 위해)

#include <iostream>
#include <algorithm>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
 
int R,C;
int ans=0;
char board[20][20]={0};
int alphabet[26]={0}; //A~Z
 
void dfs(int y,int x,int cnt){
    
    ans=max(ans,cnt);
    
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=R || nx<0 || nx>=C)
            continue;
        
        //A:65 Z:90
        int k=(int)board[ny][nx]-65;
        if(alphabet[k])
            continue;
        
        alphabet[k]++;
        dfs(ny,nx,cnt+1);
        alphabet[k]--;
        
    }
}
int main(){
    
    cin>>R>>C;
    
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++){
            cin>>board[i][j];
        }
 
    alphabet[(int)board[0][0]-65]++; //(0,0)지점 방문 체크
    dfs(0,0,1);
    
    cout<<ans<<endl;
    
    return 0;
}