[백준] 1987 알파벳(Java)

문제링크

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

문제분석

• 말은 1, 1 좌표에서 시작한다.
• 말은 상하좌우로 이동할 수 있다.
• 말은 같은 알파벳을 두번이상 지날 수 없다.
• 시작 좌표도 정답에 포함해 계산한다.

입력

보드 - 세로 R, 가로 C (1<=R,C<=20)
보드 각 칸 - 대문자 알파벳

출력

• 말이 최대한 움직일 수 있는 칸 수

풀이

• 알파벳의 중복을 체크할 ch배열 생성('Z'는 90이므로 91의 길이를 가지는 배열 생성)
• 알파벳 중복이 안되게 DFS로 탐색하며 최댓값 갱신

DFS(int r, int c, int L)

• r : 현재 행
• c : 현재 열
• L : 현재 좌표까지 움직인 칸 수

코드

import java.util.*;

public class Main {
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    static int answer = Integer.MIN_VALUE; //정답 저장할 변수

    //입력받을 변수
    static int R, C;
    static int[][] board;

    //중복을 체크할 배열
    static boolean[] ch;

    public static void main(String[] args){
        //중복 알파벳을 체크할 배열 'Z'의 값은 90이다.
        ch = new boolean[91];

        Scanner scanner = new Scanner(System.in);
        //입력을 받는다.
        R = scanner.nextInt();
        C = scanner.nextInt();
        board = new int[R][C];

        for(int i=0; i<R; i++){
            String next = scanner.next();
            for(int j=0; j<C; j++){
                board[i][j] = next.charAt(j);
            }
        }

        //깊이 우선 탐색
        ch[board[0][0]] =true;
        DFS(0, 0, 1);

        System.out.println(answer);
    }
    static void DFS(int r, int c, int L){
        //이동 가능한 방향을 찾는다.
        ArrayList<Integer> direction = canMoveDirection(r, c);
        //이동 가능 방향이 없으면 정답 갱신 후, 탐색 종료
        if(direction.size()==0) {
            answer = Math.max(answer, L);
            return ;
        } else {
            //이동 가능한 방향으로 탐색
            for (Integer i : direction) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                ch[board[nr][nc]] = true;
                DFS(nr, nc, L + 1);
                ch[board[nr][nc]] = false;
            }
        }
    }

    //이동 가능한 방향을 찾아서 반환해주는 함수
    private static ArrayList<Integer> canMoveDirection(int r, int c){
        ArrayList<Integer> direction = new ArrayList<>();
        for(int i=0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(nr<0 || nr>=R || nc<0 || nc>=C) continue;
            if(ch[board[nr][nc]]) continue;
            direction.add(i);
        }
        return direction;
    }
}