백준 1987 알파벳 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/1987

풀이는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {
    static int answer = 1;
    static char[][] map;
    static int R,C;
    static boolean[] visited;
    static int max = 0;
    
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st1.nextToken());
        C = Integer.parseInt(st1.nextToken());
        
        map = new char[R][C];
        visited = new boolean[26]; //알파벳 개수
        
        for(int r = 0 ; r < R ; r++) {
            String S = br.readLine();
            for(int c = 0 ; c < C ; c++) {
                map[r][c] = S.charAt(c);
            }
        }

        visited[map[0][0] - 'A'] = true;

        backTracking(0, 0);

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();

    }
    
    static void backTracking(int r, int c) {

        for(int i = 0 ; i < 4 ; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(isValid(nr, nc)) {
                visited[map[nr][nc] - 'A'] = true;
                answer++;
                backTracking(nr, nc);
                visited[map[nr][nc] - 'A'] = false;
                answer--;
            }
        }

        max = Math.max(answer, max);
    }

    static boolean isValid(int r, int c) {
        if(r >= 0 && r < R && c >= 0 && c < C && !visited[map[r][c] - 'A']) return true;
        return false;
    }
}

백트래킹 + DFS 문제이다.
map[][]은 char의 배열이다.
그렇기에 visited[map[r][c] - 'A'] 는,
어떤 알파벳을 방문했는지를 알려주는 배열이다.

예를 들어, A를 방문했다고 하면, (map[r][c] = 'A' 라고 하면,)
vistied[map[r][c] - 'A'] = visited['A' - 'A'] = visited[0] = true
이런식이다.

B를 방문했다고 하면, (map[r][c] = 'B' 라고 하면,)
vistied[map[r][c] - 'A'] = visited['B' - 'A'] = visited[1] = true
이다.

백트래킹을 돌아주며,
밟아온 서로 다른 알파벳의 수를 answer으로 기록했고,
max로 answer의 최댓값을 갱신시켜주었다.