(0, 0)부터 탐색을 시작하여 도착하는 칸마다 사방 탐색을 진행해야 합니다. 이 때, 방문했던 칸에 대한 처리를 visited 배열을 통해야 하는데 boolean 배열 대신 int 배열을 사용하여 visited에 대한 처리와 최대 움직인 횟수를 한 배열에 저장하였습니다.
그 방법은 다음과 같습니다.
3 7
3942178
1234567
9123532
이러한 입력이 주어졌을 때 visited 배열의 초기 모습은
-1로 초기화되어 있습니다. -1은 아직 방문하지 않은 칸임을 의미합니다.
(0, 0)부터 탐색을 진행하면 방문한 배열은 일단 0으로 값을 변경합니다.
몇 번의 이동으로 visited 배열이 이와 같은 모습이 되었을 때, (0, 6)은 네 방향 중 어디로도 이동할 수 없으므로 처음 return이 발생합니다.이 때, 해당 자리에 최대 움직인 횟수를 기록합니다. visited 배열엔 다음과 같은 모습으로 최대 움직인 횟수가 기록 됩니다.
각 자리마다 사방 탐색을 진행하였을 때 가장 이동을 많이 한 횟수만이 칸에 저장되기 때문에 (0, 3)의 경우, 아래로 갔을 때 4회, 왼쪽으로 갔을 때 2회, 오른쪽으로 갔을 때 2회 이동이 가능하므로 최댓값인 4가 기록되는 모습을 볼 수 있습니다.
추가적으로 이 문제에 주어진 조건으로 무한히 이동할 수 있다면 -1을 출력하라는 조건이 있습니다. 이는 경로 탐색 중 cycle이 발생하거나 바로 직전에 탐색한 칸으로 돌아올 수 있다면 -1을 출력하라는 것으로 해석할 수 있습니다. 따라서 이 코드에선 경로를 탐색하던 중 visited값이 0인 칸을 만나면 cycle이 생긴 것이고 -1을 출력하면 됩니다. 현재 탐색에서 visited가 0이 아닌 칸은 탐색이 종료된 지점이고 현재의 경로로 다시 돌아온다고 보장할 수 없기 때문입니다.
이러한 내용을 코드로 짜면 다음과 같습니다.
import java.io.*;
import java.util.Arrays;
//백준 1103 게임
public class b1103 {
static int N, M;
static int board[][];
static int visited[][];
static boolean cycle;
static int dx[] = {1, -1, 0, 0};
static int dy[] = {0, 0, 1, -1};
public static int dp(int x, int y) {
if(x >= 0 && x < N && y >= 0 && y < M) {
if(visited[x][y] == -1) {
int cal = 0; // 사방 탐색을 하고 사방 중 최대로 많이 이동한 횟수
if(board[x][y] == -1) {
return 0;
}
else {
visited[x][y] = 0; // 일단 방문 처리
for(int i = 0;i < 4;i++) {
int nx = x + dx[i] * board[x][y];
int ny = y + dy[i] * board[x][y];
cal = Math.max(cal, dp(nx, ny) + 1);
}
return visited[x][y] = cal;
}
} else if(visited[x][y] == 0) {
cycle = true;
} else {
return visited[x][y];
}
}
return 0;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str[] = br.readLine().split(" ");
N = Integer.parseInt(str[0]);
M = Integer.parseInt(str[1]);
board = new int[N][M];
visited = new int[N][M];
for(int i = 0;i < N;i++) Arrays.fill(visited[i], -1);
// H : -1로 표시
for(int i = 0;i < N;i++) {
str = br.readLine().split("");
for(int j = 0;j < str.length;j++) {
if(str[j].equals("H")) board[i][j] = -1;
else board[i][j] = Integer.parseInt(str[j]);
}
}
dp(0, 0);
if(cycle) System.out.println(-1);
else System.out.println(visited[0][0]);
}
}