[ BOJ ][JAVA][1103] 게임

www.acmicpc.net/problem/1103

1103번: 게임

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	9543	1897	1302	19.116%

문제

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 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

코드

/*
    게임
    50 * 50 맵에서 완전탐색을 하는 것은 worst case로 이론상 2500! 에 가까운 경우의 수가 발생할 수 있다.
    여러 조건으로 가지치기가 될 경우에서 50*50 맵은 bfs,dfs의 마지노선이다.

    따라서 보다 간단한 형태의 dp 등을 접목해 메모이제이션을 통해 효율성을 높여야한다.
    이 문제는 bfs+dp를 하게 되면 백트래킹이 매우 까다로우므로 "dfs + dp"를 활용한다.
*/
import java.io.*;
import java.util.*;

public class p1103 {
    static int n, m, answer;
    static boolean[][] visited;
    static int[][] board, dp;
    static boolean flag;
    // dir : 북 동 남 서 (북쪽에서부터 시계방향)
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    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[55][55];
        dp = new int[55][55];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                char tmp = line.charAt(j);
                if (tmp == 'H') {
                    board[i][j] = 0;
                } else {
                    board[i][j] = tmp - '0';
                }
            }
        }

        flag = false;
        answer = 0;
        visited = new boolean[55][55];
        visited[0][0] = true;
        go(0, 0, 1);

        System.out.println(flag ? -1 : answer);
    }

    static void go(int r, int c, int cnt) {
        if (cnt > answer) {
            answer = cnt;
        }
        // 가지치기용 DP배열에 현재 카운트 메모
        dp[r][c] = cnt;
        for (int i = 0; i < 4; i++) {
            int jump = board[r][c];
            int nr = r + dr[i] * jump;
            int nc = c + dc[i] * jump;
            if (OOB(nr, nc) || board[nr][nc] == 0) continue;
            if (visited[nr][nc]) {
                flag = true;
                return;
            };
            // 메모이제이션을 통해서 기억해놨다가 해당 칸이 지금보다 많다면 해당 루트로 탐색할 필요가 없다.
            if (dp[nr][nc] > cnt) continue;

            visited[nr][nc] = true;
            go(nr, nc, cnt + 1);
            visited[nr][nc] = false;
        }
    }


    static boolean OOB(int r, int c) {
        return r < 0 || c < 0 || r >= n || c >= m;
    }
}