[백준] 1987번 - 알파벳 (Gold 4)

문제 링크

백준 1987번 - 알파벳 (Gold 4)

문제 설명

R x C 크기의 보드가 있다. R과 C는 20 이하의 자연수이다.
보드의 각 칸에는 대문자 알파벳이 하나씩 적혀있고, 1행 1열에 말이 놓여있다.
말은 한 번에 상하좌우로 한 칸씩만 이동이 가능하며, 같은 알파벳이 적힌 칸은 두 번 지날 수 없다.
말이 지날 수 있는 칸의 최대 개수를 구하시오. 단, 출발한 칸도 지나간 칸으로 센다.

정답 코드 및 설명

알파벳이 26개이므로 말이 지날 수 있는 칸은 최대 26개이다.
보드가 최대 400칸이고, 같은 알파벳이 적힌 칸을 두 번 지날 수 없는 제약도 있으므로 가능한 전체 경로의 수가 아주 많지는 않을 것이라고 짐작할 수 있다. 모든 경로를 탐색하는 백트래킹을 수행하자. 문제의 조건처럼 이미 지나온 알파벳이 있는 방향으로는 진행하지 않는다.

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

public class BOJ1987 {
    final int[][] NEXT = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int r, c;
    char[][] board;
    boolean[] isChecked = new boolean[26];

    void input() 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());
        String row;
        board = new char[r][];
        for (int i = 0; i < r; i++) {
            row = br.readLine();
            board[i] = row.toCharArray();
        }
    }

    int maxLength = 0, length = 0;

    void backtracking(int i, int j) {
        isChecked[board[i][j] - 'A'] = true;
        length++;
        if (length > maxLength) maxLength = length;
        int nextI, nextJ;
        for (int k = 0; k < 4; k++) {
            nextI = i + NEXT[k][0];
            nextJ = j + NEXT[k][1];
            if (!isValid(nextI, nextJ)) continue;
            if (isChecked[board[nextI][nextJ] - 'A']) continue;
            backtracking(nextI, nextJ);
        }
        isChecked[board[i][j] - 'A'] = false;
        length--;
    }

    boolean isValid(int i, int j) {
        return i >= 0 && i < r && j >= 0 && j < c;
    }

    void solution() throws IOException {
        input();
        backtracking(0, 0);
        System.out.println(maxLength);
    }

    public static void main(String[] args) throws IOException {
        new BOJ1987().solution();
    }
}