[백준/DP-DFS] 1103 게임 - 자바

문제

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

1103번: 게임

 

풀이

사이클을 체크하기 위한 visited 배열,

이동 카운트 횟수를 저장하기 위한 dp배열

을 이용하여 탐색할 때 이동 카운트 횟수가 저장된 배열과 비교하여 

이동할 곳의 카운트 위치가 현재 탐색하고 있는 경로의 카운트보다 많다면 해당 지점을 탐색할 필요가 없음.

이를 이용하여 시간초과를 회피 할 수 있음

 

세부설명은 주석 참고

import java.util.*;
import java.io.*;

public class BOJ_1103_G2_게임 {
    static int N, M, ans;
    static boolean cycleCheck; // 무한사이클 체크
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
    static int[][] arr; // 이동거리 저장
    static int[][] dp; // 해당 지점에서 최대로 이동했던 카운트 저장
    static boolean[][] visited; // 사이클 체크용 방문 배열

    public static void main(String[] args) throws Exception {
        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 int[N][M];
        dp = new int[N][M];
        visited = new boolean[N][M];
        ans = 0;
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                String input = String.valueOf(s.charAt(j));
                // 구멍일 때 -1 로 저장
                if(input.equals("H")) {
                    arr[i][j] = -1;
                } else {
                    arr[i][j] = Integer.parseInt(input);
                }
            }
        }
        // end :: input

        // sol
        dfs(0,0,1);

        System.out.println(cycleCheck ? "-1" : ans);

    }

    private static void dfs(int y, int x, int moveCnt) {
        // 재귀시마다 최대값 측정
        ans = Math.max(moveCnt, ans);
        dp[y][x] = moveCnt;
        int dist = arr[y][x];
        // 4방면 방문
        for (int d = 0; d < 4; d++) {
            int ny = y + dist * dy[d];
            int nx = x + dist * dx[d];
            if(ny >= N || nx >= M || ny < 0 || nx < 0 || arr[ny][nx] == -1) continue;
            // 사이클이 형성되면 메서드 종료
            if(visited[ny][nx]) {
                cycleCheck = true;
                return;
            }
            // 백트래킹 -> 이동할 지점이 현재 탐색한 경로 보다 더 많이 이동 카운트가 있으면 현재 경로를 탐색할 필요가 없음
            if(dp[ny][nx] > moveCnt) continue;

            // 재귀
            visited[ny][nx] = true;
            dfs(ny, nx, moveCnt + 1);
            visited[ny][nx] = false;
        }
    }

}