[BOJ/Back-Tracking] 백준 1987 - 알파벳 (Java)

1987 - 알파벳

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

문제

세로 R칸, 가로 C칸 보드/ 각 칸에 대문자 알파벳 적혀 있고 좌측 상단 (1행 1열)에 말이 놓여 있음
말은 상하좌우 인접한 네 칸 중 한 칸으로 이동할 수 있음
새로 이동한 칸에 적혀 있는 알파벳은 지나온 모든 칸에 적혀 있는 알파벳과 달라야 함 (같은 알파벳 적힌 칸 두 번 지날 수 없음)

입력
첫째 줄: R, C (1 <= R, C <= 20)
둘째 줄 ~ R개 줄: 보드에 적혀 있는 C개의 대문자 알파벳
출력: 말이 지날 수 있는 최대 칸 수

---

풀이

알파벳 방문 여부 체크

static boolean[] visited = new boolean[26];
visited[board[0][0] - 'A'] = true;

---

코드

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

// 알파벳
public class boj_1987 {
    static int R, C;
    static char[][] board;
    static boolean[] visited = new boolean[26];
    static int max = 0;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void dfs(int x, int y, int cnt) {
        max = Math.max(max, cnt);

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;

            char next = board[nx][ny];
            int idx = next - 'A';

            if (!visited[idx]) {
                visited[idx] = true;
                dfs(nx, ny, cnt + 1);
                visited[idx] = false;
            }
        }
    }

    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());

        board = new char[R][C];
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                board[i][j] = line.charAt(j);
            }
        }

        visited[board[0][0] - 'A'] = true;
        dfs(0, 0, 1);

        System.out.println(max);
    }
}