#백준_1987 알파벳 - Java

#유형 : DFS

#전형적인 dfs , 백트래킹 문제

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1987 {
    static int max = 0;
    static int R,C;
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static char arr[][];
    static boolean use[] = new boolean[26];
    static boolean visit[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];
        visit = new boolean[R][C];
        for(int i=0; i<R; i++) {
            String str = br.readLine();
            for(int j=0; j<C; j++) {
                arr[i][j] = str.charAt(j);
            }
        }
        visit[0][0]=true;
        int next = arr[0][0]-65;
        use[next]=true;
        dfs(0,0,1);
        
        System.out.println(max);
    }
    
    public static void dfs(int i,int j, int cnt) {
        max = Math.max(max, cnt);
        
        for(int d=0; d<4; d++) {
            int newX = j + moveX[d];
            int newY = i + moveY[d];
            
            
            if(0<=newX && newX<C && 0<=newY && newY<R && !visit[newY][newX]) {
                int next = arr[newY][newX]-65;
                if(!use[next]) {
                    visit[newY][newX] = true;
                    use[next] = true;
                    dfs(newY,newX,cnt+1);
                    use[next] = false;
                    visit[newY][newX] = false;
                }
            }
        }
    }
}