[BOJ] 1987 : 알파벳(Java)

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

---

💡풀이

처음에는 BFS로 접근을 시도했지만, 모든 가능한 경로를 탐색한 뒤 그 중 가장 길이가 긴 것을 선택해야하기 때문에 DFS를 이용해 풀이했다. 

1. 먼저, (0,0)에서 출발해 상하좌우로 이동하며 범위에 벗어나거나 이미 방문한 알파벳인 경우는 넘어간다. 
2. 만약, 방문이 가능하고 아직 만나지 않은 알파벳이라면 str 문자열에 알파벳을 추가하고 재귀로 DFS를 실행한다. 
   1. 이때 재귀로 실행되는 DFS가 종료되면 해당하는 위치의 방문을 false로 처리해 다시 방문이 가능하게끔 한다. 
3. 매번 DFS가 실행될 때마다 알파벳의 길이를 max으로 갱신시켜준다.

전체적인 코드는 다음과 같다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static int R, C;
    public static String[][] graph;
    public static boolean[][] visited;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};
    public static int result = 0;

    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());
        graph = new String[R][C];
        visited = new boolean[R][C];
        for(int i=0;i<R;++i){
            graph[i] = br.readLine().split("");
        }

        DFS(0,0, graph[0][0], 1);
        System.out.println(result);
    }

    public static void DFS(int x, int y, String str, int count){

        result = Math.max(result, count);

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= R || ny < 0 || ny >= C||visited[nx][ny]) {
                continue;
            }
            if (!str.contains(String.valueOf(graph[nx][ny]))) {
                visited[nx][ny] = true;
                DFS(nx, ny, str+graph[nx][ny],count + 1);
                visited[nx][ny] = false;
            }
        }

    }

}