[BOJ 1103] 게임(Java, DFS, DP, Cycle)

www.acmicpc.net/problem/1103

1103번: 게임

 

## 접근

---

이 문제는 정답률에 비해서 어렵지 않은 문제이다. 보드의 크기만큼의 DP를 선언해주고, DP의 값을 갱신하면서 가장 큰 이동 횟수를 구해주면 된다. 

 

 

 

DP[nr][nc] = DP[r][c] + 1

 

 

 

nr, nc는 r, c에서 이동할 수 있는 신규 점을 의미한다. +1은 이동 횟수가 더해짐을 의미한다. 어떤 nr, nc를 접근할 때, 기존에 가진 값을 갱신하지 못하면 이동할 필요가 없다.

 

 

 

이 문제에서는 위의 개념만으로 풀 수 없는 이유가, 무한히 이동이 가능하면 -1을 출력해야 한다. 무한히 이동 가능함을 미리 판단하고 -1을 출력하도록 코드를 작성해야 한다.

 

 

 

그래프 문제이므로, DFS를 이용해서 방문된 점이 재방문된다면 싸이클(루프)이 형성됨을 의미한다. 이 개념만 가지고 코드를 작성하면 시간초과가 발생한다. 왜냐하면, 어떤 점이 싸이클이 없다고 판단이 된 후에, 다른 점의 경로에 의해 재 방문되면 또 다시 모든 과정들을 검사하기 때문이다.

 

 

 

싸이클이 없다고 판단된 점은, 이후에 방문되면 더 이상 검사되지 않아야 한다. 따라서, 방문을 표시하는 배열 이외에 싸이클이 없다고 판단됨을 기억하는 배열도 필요하다.

 

 

 

위의 내용들을 코드에 녹여내면 된다!

 

 

## 해설코드

---

 

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static char[][] map;
    static int[][] dp;
    static int[][] op = {{1,0},{-1,0},{0,1},{0,-1}};
    static int X;
    static String[] sArr;
    static String str;
    static int answer = 0;
    static boolean[][] chk;
    static boolean[][] cycle;
    
    static boolean loopChk(int r, int c){
        int val = Integer.valueOf(map[r][c] - '0');
 
        for(int i = 0; i < op.length; i++){
            int nr = r + val * op[i][0];
            int nc = c + val * op[i][1];
 
            if(!rangeChk(nr, nc)) continue;
            
            if(map[nr][nc] == 'H') continue;
            
            if(!cycle[nr][nc]){
                if(!chk[nr][nc]){
                    chk[nr][nc] = true;
                    if(loopChk(nr, nc)) return true;
                    chk[nr][nc] = false;
                }else
                    return true;
            }
        }
        
        cycle[r][c] = true;
        return false;        
    }
    
    static boolean rangeChk(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < M;
    }
    
    static void move(int r, int c){
        int val = Integer.valueOf(map[r][c] - '0');
        
        for(int i = 0; i < op.length; i++){
            int nr = r + val * op[i][0];
            int nc = c + val * op[i][1];
            
            answer = Math.max(answer, dp[r][c] + 1);
            
            if(!rangeChk(nr, nc)) continue;
            
            if(map[nr][nc] == 'H') continue;
            
            if(dp[r][c] + 1 > dp[nr][nc]){
                dp[nr][nc] = dp[r][c] + 1;
                move(nr, nc);
            }
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        sArr = br.readLine().split(" ");
        
        N = Integer.valueOf(sArr[0]);
        M = Integer.valueOf(sArr[1]);
        
        map = new char[N][M];
        dp = new int[N][M];
        chk = new boolean[N][M];
        cycle = new boolean[N][M];
        
        for(int i = 0; i < N; i++){
            str = br.readLine();
            for(int j = 0; j < M; j++){
                map[i][j] = str.charAt(j);
            }
        }
 
        if(loopChk(0, 0)){
            System.out.println("-1");
            return;
        }
        
        move(0, 0);
        
        bw.write(answer + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}