[java] 1987번 알파벳

1. 문제 링크 및 문제

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

1-1 문제 요약

: 중복되지 않게 지날 수 있는 최대 알파벳 수

2. 해결 방법 생각해보자 ...

방문했는 지 판별 방법
: 알파벳은 총 26개 이므로, boolean visited[26]를 만들어 판별

3. 코드

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

public class Main {

    static int R,C;
    static int[][] arr;
    static boolean[] visited = new boolean[26];
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static int MaxResult = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        // 값 입력받기 -->
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new int[R][C];

        for(int i=0;i<R;i++){
            String str = br.readLine();
            for(int j=0;j<C;j++){
                arr[i][j] = str.charAt(j)-'A';
            }
        }
        //<--
        
        dfs(0,0,1);
        System.out.println(MaxResult);
    }

    public static void dfs(int x, int y, int count){
        MaxResult = Math.max(MaxResult, count);
        visited[arr[x][y]] = true;

        for(int i=0;i<4;i++){
            int xx = x+dx[i];
            int yy = y+dy[i];
            if(xx<0 || xx>=R || yy<0 || yy>=C || visited[arr[xx][yy]]) continue;
            dfs(xx,yy,count+1);
            visited[arr[xx][yy]]=false;
        }
    }
}

예시 ) 백준 예시 2번
3 6
HFDFFB
AJHGDH
DGAGEH

dfs(0,0,1) 일 때 -> (0,1,2) (1,0,2) 가능

dfs(0,1,2) 일 때 -> (1,1,3) (0,2,3) 가능

dfs(0,2,3) 일 때

-> dfs(0,1,2) 일 때로 return 하여, (1,1,3) 실행
dfs(1,1,3) 일 때

dfs(1,0,4)일 때

dfs(2,0,5)일 때

dfs(2,1,6) 일 때

입력받을 때 charAt - 'A' 를 해주어 0,1,2, ...이렇게 들어왔지만 편의상 visited[알파벳]으로 표기하였다.
가다가 return 되는 dfs 들은 생략하였으며, 최대 count 를 구해내는 dfs 를 표로 그려보았다.
count == visited true 알파벳의 개수