[백준] 1987번 알파벳

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

1987번: 알파벳

문제 :  1행 1열의 말이 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 문제 풀이 : dfs를 활용하여 풀었습니다. 지나온 알파벳과 다른 알파벳에 들어간 걸 체크해주기 위한 check 배열을 사용했습니다. A~Z 까지  배열 크기를 26으로 지정해주고 아스키코드 문자로 사용하였습니다. count 변수로 최대한 몇 칸 갔는지 세어주고, 그 중 가장 최대의 숫자를 answer 변수에 넣어 출력해줍니다. 몰랐던 점 : dfs 후, count를 초기화 해주는 것이 아닌 다시 --를 해주어 세주자.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static int R,C,answer = Integer.MIN_VALUE, count = 1;
	static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
	static char[][] map;
	static boolean[][] visited;
	static int[] check;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		map = new char[R][C];
		visited = new boolean[R][C];
		check = new int[26];
		
		for (int i = 0; i < R; i++) {
			String s = sc.next();
			for (int j = 0; j < C; j++) {
				map[i][j] = s.charAt(j);
			}
		}//end of input
		dfs(0,0);
		
		System.out.println(answer);
	}//end of main

	public static void dfs(int x, int y) {
		visited[x][y] = true;
		check[map[x][y]-65] = 1;
		
		for (int i = 0; i < dir.length; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			
			if(isInside(nx,ny) && !visited[nx][ny] && check[map[nx][ny]-65] == 0) {
				count ++;
				dfs(nx,ny);
				check[map[nx][ny]-65] = 0;
				visited[nx][ny] = false;
				count--;
			}
			
		}
		answer = Math.max(answer, count);
	
	}

	public static boolean isInside(int x, int y) {
		return x>=0 && x<R && y>=0 && y<C;
	}
}