문제 출처: https://www.acmicpc.net/problem/1987
문제
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int result;
private static int temp;
private static int[][] directions = {
{ -1, 0 }, // 상
{ 1, 0 }, // 하
{ 0, -1 }, // 좌
{ 0, 1 }, // 우
};
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int R = Integer.parseInt(tokenizer.nextToken());
int C = Integer.parseInt(tokenizer.nextToken());
char[][] board = new char[R][C];
for (int i = 0; i < R; i++) {
board[i] = reader.readLine().toCharArray();
}
boolean[] flag = new boolean[26]; // 'A' -> 0
dfs(board, flag, 0, 0, R, C);
System.out.println(result);
}
private static void dfs(char[][] board, boolean[] flag, int row, int col, int R, int C) {
flag[board[row][col] - 'A'] = true; // 사용 처리
temp++;
for (int i = 0; i < 4; i++) {
int dy = row + directions[i][0];
int dx = col + directions[i][1];
if (dy >= 0 && dy < R && dx >= 0 && dx < C) {
if (!flag[board[dy][dx] - 'A']) {
dfs(board, flag, dy, dx, R, C);
}
}
}
flag[board[row][col] - 'A'] = false; // 사용 처리
result = Math.max(result, temp);
temp--;
}
}