[BOJ] 1987. 알파벳

백트래킹을 이용하여 경로를 찾는 문제이다.

백트래킹 DFS 경로문제는 일반 재귀를 사용하는 DFS와는 다르게 방문체크를 호출전에 해줘야한다는 점이 특징이다. 그후 호출이 끝난다면 당시 방문해제를 해줘야한다. 이점을 유의한다면 쉽게 풀수 있었던 문제이다.

package online.practice;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1987_알파벳 {
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int R,C;
    
    static char[][] map;
    static boolean[] check;
    
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        
        map=new char[R][C];
        for(int i=0;i<R;i++) {
            String str=br.readLine();
            for(int j=0;j<C;j++) {
                map[i][j]=str.charAt(j);
            }
        }
        
        check=new boolean[26];
        answer=0;
        check[map[0][0]-'A']=true;
        dfs(0,0,1);
        System.out.println(answer);
        
    }
    static void dfs(int i,int j,int len) {
        answer=Math.max(len, answer);
        
        
        for(int dir=0;dir<4;dir++) {
            int nextI=i+di[dir];
            int nextJ=j+dj[dir];
            
            if(nextI<0 || nextI>=R || nextJ<0 || nextJ>=C)
                continue;
            
            if(check[map[nextI][nextJ]-'A']==false) {
                check[map[nextI][nextJ]-'A']=true;
                dfs(nextI,nextJ,len+1);
                check[map[nextI][nextJ]-'A']=false;
            }
            
        }
        
    }
    
}