[백준 알고리즘 - 1987] 알파벳 - java(백트래킹)

최대로 이동할 수 있는 칸은 20*20 = 400으로 크지 않고

상태 비교만 하면 되기 때문에 완전 탐색으로 문제 해결이 가능하다.

단, 최장경로이기 때문에 현재 탐색이 끝났을 때 지금까지의 max 경로길이와 비교하여 업데이트 해주고 모든 탐색이 끝날 때까지 종료하면 안된다.

상태 저장은 각 알파벳의 아스키코드를 이용하였고 A가 65이기 때문에 -65를 해주어 0-25 인덱스에 저장할 수 있도록 설정하였다.

import java.util.Scanner;

public class Main {
	static int max=0;
	public static void Alph(char[][] arr, boolean[] check, int idx, int count){
		
		int x=idx/arr[0].length;
		int y=idx%arr[0].length;
		

			if(max<count) //최장경로 업데이트
				max=count;

		
	
			
			if(x>0  && check[(int)(arr[x-1][y])-65]==false){//위로 갈 수 있는지?
				 check[(int)(arr[x-1][y])-65]=true;
				 Alph(arr,check, idx-arr[0].length, count+1);
				 check[(int)(arr[x-1][y])-65]=false;
			}
			if(y<arr[0].length-1 && check[(int)(arr[x][y+1])-65]==false){//오른쪽으로 갈 수 있는지?
				 check[(int)(arr[x][y+1])-65]=true;
				 Alph(arr,check, idx+1, count+1);
				 check[(int)(arr[x][y+1])-65]=false;
			}
			if(y>0 && check[(int)(arr[x][y-1])-65]==false){//왼쪽으로 갈 수 있는지?
				 check[(int)(arr[x][y-1])-65]=true;
				 Alph(arr,check, idx-1, count+1);
				 check[(int)(arr[x][y-1])-65]=false;
			}
			if(x<arr.length-1 && check[(int)(arr[x+1][y])-65]==false){//아래로 갈 수 있는지?
				 check[(int)(arr[x+1][y])-65]=true;
				 Alph(arr,check, idx+arr[0].length, count+1);
				 check[(int)(arr[x+1][y])-65]=false;
			}
		

	}

	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		int R=scan.nextInt();
		int C=scan.nextInt();
		scan.nextLine();
		char[][] arr=new char[R][C];
		
		for(int i=0; i<R; i++){
			String line=scan.nextLine();
			for(int j=0; j<C; j++){
				arr[i][j]=line.charAt(j);
			}
		}
		
		boolean[] check=new boolean[26];
		check[(int)(arr[0][0])-65]=true;
		Alph(arr,check, 0, 1);
		System.out.println(max);

	}

}