[Java][백준 1103] 게임

문제

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

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

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

입력

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

---

접근 방식

원래 bfs를 이용해서, 최대 개수를 찾았습니다. 하지만 bfs 방법으로는 최대값은 찾을 수 있어도, 싸이클이 있는지를 판단할 수 없었습니다.
bfs를 사용하여 탐색을 할 때는, 방문한 장소가 true일때, 싸이클이 있다고 장담할 수 없었기 때문입니다.

따라서 dfs 방법으로 풀어야겠다는 생각을 하게 되었고, 재귀 방식으로 찾은 최댓값을 저장하기 위해서 dp를 사용했습니다.

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

public class Main {

    /*
     * bfs로는 사이클을 찾기 힘들 것 같다.
     * dfs로 방문했던 곳을 true처리하고 다시 되돌아오면 false 처리를 함으로써
     * true일 때 사이클인 것을 기준으로 할 수 있도록 해야한다.
     * 또한 재귀를 통해 여러번 방문하는 개수를 세서 최대 이동 횟수를 기억해둬야한다(dp)
     */

    static int m, n, max, cnt;
    static int[] dx = {0, 0, -1, 1}, dy = {1, -1, 0, 0};
    static char[][] arr;
    static int[][] board, dp;
    static boolean isInfinite; // 무한으로 움직일 수 있는지 확인
    static boolean[][] visited;

    public static void main(String[] args) throws NumberFormatException, 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());
        arr = new char[n][m];
        board = new int[n][m];
        dp = new int[n][m];
        visited = new boolean[n][m];

        //공백 없이 값이 들어오기 때문에, char의 형태의 배열에 입력
        for (int i = 0; i < n; i++) {
            arr[i] = br.readLine().toCharArray();
        }

        //int 배열을 만들어서, 형변환
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(arr[i][j] == 'H') board[i][j] = -1;
                else board[i][j] = (int)arr[i][j] - '0';
            }
        }

        visited[0][0] = true;

        dfs(0, 0, 1);

        if(isInfinite) System.out.println(-1);
        else System.out.println(max);
    }

    public static void dfs(int x, int y, int cnt) {
        //최대 이동 횟수가 갱신되었다면, max에 저장
        if(cnt > max) max = cnt;

        //현재 이동 횟수를 dp 배열에 저장
        dp[y][x] = cnt;

        for (int i = 0; i < 4; i++) {
            //보드판의 숫자만큼 사방탐색
            int nx = dx[i]*board[y][x] + x;
            int ny = dy[i]*board[y][x] + y;

            //보드판 밖으로 나가거나, 구멍인 경우에 넘어감
            if(nx >= m || ny >= n || nx < 0 || ny < 0 || board[ny][nx] == -1) continue;

            //이미 방문한 장소라면, 싸이클이므로 재귀를 멈추고, -1 출력
            if(visited[ny][nx]) {
                isInfinite = true;
                return;
            }

            //방문하게 될 장소의 저장된 이동횟수가 더 크다면, 방문하지 않는다.
            if(dp[ny][nx] <= cnt) {
                //작거나 같다면, 방문처리를 해주고, dfs 탐색을 시작한다.
                visited[ny][nx] = true;
                dfs(nx, ny, cnt+1);
                visited[ny][nx] = false;
            }
        }
    }
}

https://www.acmicpc.net/problem/1103

1103번: 게임