[백준 1987번] 알파벳 / Java

[boj 1987번] 알파벳

 

문제 ::

https://www.acmicpc.net/submit/1987/18450536

r행 c열의 표 모양의 보드가 있다. 좌측 최 상단(1,1 or 0,0)에서 시작해 말이 최대한 몇 칸을 이동 할 수 있는지 구하는 문제.

 

int board[][] : 입력 되는 보드

boolean check[] : 방문한 알파벳

x, y : 현재 위치

ans : 최대 방문 가능한(이동 가능한) 칸의 수

 

go(board, check, nx, ny, max+1)

 

 

public class Main {
    public static final int[] dx = {0, 0, 1, -1};
    public static final int[] dy = {1, -1, 0, 0};
    static int ans, next = 0;
    public static void go(String[] board, boolean[] check, int x, int y, int next) {
    	if (ans < next) {
            ans = next;
        }
        
        for (int k=0; k<4; k++) {
            int nx = x+dx[k];
            int ny = y+dy[k];
            if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length()) {
                if (check[board[nx].charAt(ny)-'A'] == false) {
                    check[board[nx].charAt(ny)-'A'] = true;
                    go(board, check, nx, ny, next+1);
                    check[board[nx].charAt(ny)-'A'] = false;
                }
            }
        }
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        String[] board = new String[n];
        for (int i=0; i<n; i++) {
            board[i] = sc.nextLine();
        }
        boolean[] check = new boolean[26];
        check[board[0].charAt(0)-'A'] = true;
        go(board, check, 0,0,1);
        System.out.println(ans);
    }
}