문제
https://www.acmicpc.net/problem/1103
형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.
일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.
동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.
만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.
보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.
입력
줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.
예제 입력 1
3 7
3942178
1234567
9123532
예제 출력 1
5
예제 입력 2
1 10
2H3HH4HHH5
예제 출력 2
4
예제 입력 3
4 4
3994
9999
9999
2924
예제 출력 3
-1
예제 입력 4
4 6
123456
234567
345678
456789
예제 출력 4
4
예제 입력 5
1 1
9
예제 출력 5
1
예제 입력 6
3 7
2H9HH11
HHHHH11
9HHHH11
예제 출력 6
2
접근
처음에 DP인가? 했었는데, 이 문제처럼 격자인데 상하좌우로 모두 이동할 수 있는 경우에는 어느 방향에서 왔는지를 알 수 없어 메모이제이션이 불가하다고 해서 DP로 못 풀 거라고 1차원적으로 생각했었다.
그래서 그냥 DFS로 풀었는데 시간 초과가 나서 분류를 보니까 DP 문제라는 거다...
생각해 보니까, 이 문제에서 메모이제이션해야 할 값은 지나온 경로나 방향에 전혀 의존하지 않고, 오직 동전을 움직인 횟수에만 의존하기 때문에 어느 방향에서 왔는지 따위는 전혀 영향을 주지 않았다.
무작정 안 된다고 생각하지 말고 생각이란 걸 좀 하자...
아무튼 그래서 기존에 DFS(재귀)로 구현한 코드에 메모이제이션 로직을 추가해서 코드를 수정했다.
이 문제에서 또 고민해봐야 하는 것이 사이클 판별이다. 사실 사이클 판별이라고 해서 대단한 건 없고 그냥 백트래킹 식으로 visited 배열을 관리하면서 visited[i][j]가 true인 위치에 다시 도달했다면, 왔던 자리로 다시 돌아올 수 있다는 뜻이니 사이클이 존재한다는 걸 알 수 있다. 사이클이 존재한다는 건 무한 번 움직일 수 있다는 뜻이니 -1을 출력해주면 된다.
구현
import java.io.*;
import java.util.*;
class Main {
static int N;
static int M;
static int[][] board;
static boolean[][] visited;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new int[N][M];
visited = new boolean[N][M];
dp = new int[N][M];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
board[i][j] = (input.charAt(j) == 'H')? 0 : input.charAt(j) - '0';
dp[i][j] = -1;
}
}
visited[0][0] = true;
System.out.println(dfs(0, 0));
}
private static int dfs(int row, int col) {
if (dp[row][col] >= 0) {
return dp[row][col];
}
if (board[row][col] == 0) {
return 0;
}
int[] dx = {-1 * board[row][col], board[row][col], 0, 0};
int[] dy = {0, 0, -1 * board[row][col], board[row][col]};
for (int i = 0; i < 4; i++) {
int nextRow = row + dx[i];
int nextCol = col + dy[i];
if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) {
dp[row][col] = Math.max(dp[row][col], 1);
continue;
}
if (visited[nextRow][nextCol]) {
System.out.println(-1);
System.exit(0);
}
visited[nextRow][nextCol] = true;
dp[row][col] = Math.max(dp[row][col], dfs(nextRow, nextCol) + 1);
visited[nextRow][nextCol] = false;
}
return dp[row][col];
}
}
