[알고리즘][DFS][1987] 알파벳

[알고리즘][DFS][1987] 알파벳

문제

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

풀이

문제 자체를 이해를 잘못 이해해서 몇 번을 헤맸다. DFS로 풀되 다른 케이스를 체크하기 위해 백트래킹을 이용해주면 더 쉽게 풀 수 있는 문제이다.

0,0 (좌측상단)에서 출발해 가장 멀리갈 수 있는 방법을 탐색하는 문제이다. 

코드

package algorithm_DFS;
 
import java.util.Scanner;
 
public class q_1987 {
    static int r;
    static int c;
    static int[][] arr;
    static int[] check;
    static int[][] arr_check;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int cnt = 0;
    static int max = 0;
    public static void dfs (int m, int n, int cnt) {
    
        if(max<cnt) max = cnt;
        
        for(int i=0;i<4;i++) {
            int nx = m + dx[i];
            int ny = n + dy[i];
            
            if(nx>=0 && nx<r && ny>=0 && ny<c) {
                int k = arr[nx][ny];
                if(check[k]==0) {
                    check[k]++;
                    dfs(nx,ny,cnt+1);
                    check[k]--; // 다른 경로도 탐색 가능하도록 다시 빼준다.
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        r = scan.nextInt();
        c = scan.nextInt();
        scan.nextLine();
        arr = new int[r][c];
        check = new int['Z'-'A'+1];
        for(int i=0;i<r;i++) {
            char[] tmp = scan.nextLine().toCharArray();
            for(int j=0;j<c;j++) {
                char apb = tmp[j];
                arr[i][j] = (int)apb-'A';
            }
        }
        max = 0;
        check[arr[0][0]]++;
        dfs(0,0,1);
        System.out.println(max);
    }
 
}