[Algorithm/Java][백준] 1987번 알파벳

[BOJ] 1987번 알파벳

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

문제 접근

가로 R, 세로 C로 된 보드에 대문자 알파벳이 적혀있고, 가장 왼쪽 위부터 알파벳 당 한번씩만 방문해서 가장 멀리 갈 수 있는 길이를 구하는 문제이다.
처음에는 아무생각 없이 bfs로 했다가 생각해보니까 dfs가 더 맞는 것 같아서 방향을 틀었다.
처음에는 보드에 방문 여부를 저장하는 isVisited와 알파벳 방문 여부를 저장하는 alphabetVisited를 사용하려 했는데, 생각해보니까 한번 방문한 알파벳은 방문하지 못하니까 보드에 방문여부를 저장할 필요가 없고, 경로를 String으로 계속 추가해가면서 하면 알파벳 방문 여부도 따로 저장하지 않아도 될 것 같아서 dfs에 가려는 x,y와 지금까지의 경로를 담은 path를 매개변수로해서 코드를 작성하였다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ1987 {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char[][] alphabet;
    static int R,C;
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        R = Integer.parseInt(s[0]);
        C = Integer.parseInt(s[1]);
        alphabet = new char[R][C];
        for(int i = 0; i<R; i++){
            alphabet[i] = br.readLine().toCharArray();
        }
        dfs(0, 0, String.valueOf(alphabet[0][0]));
        System.out.println(answer);
    }
    public static void dfs(int x, int y, String path) {
        answer = Math.max(answer,path.length());
        for(int i = 0; i<4; i++){
            int next_x = x + dx[i];
            int next_y = y + dy[i];
            if(isIn(next_x,next_y)) continue;
            if(path.indexOf(alphabet[next_x][next_y]) != -1) continue;
            dfs(next_x, next_y, path+alphabet[next_x][next_y]);
        }
    }
    public static boolean isIn(int x, int y){
        return x<0 || x >= R || y<0 || y>=C;
    }

}