문제링크

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

구현방법

게임의 방법

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

동전이 구멍에 빠지거나 보드의 바깥으로 나가면 종료.

N과 M은 최대 50

숫자는 1 부터 9까지

H는 구멍

만약 동전을 무한정 움직일 수 있다면 -1 출력

• 무한정의 조건을 알아야함.
  • 중복 움직임이 가능한거같다.
  • 이동하는 숫자가 같은 숫자일 경우 -> 무한정 움직임 여기서 끝남.

끝나는 조건

• 홀에 빠지던가 맵을 나가는 거 밖에 없는 경우
• 무한정으로 움직인다는 것을 알아챈 경우

---

어떻게 움직일 것인가?

탐색 알고리즘으로 움직인다. DFS를 이용한다.

---

시간초과가 발생해서 생각하지 못한 부분을 찾아봤더니 다른분이 같은 방법을 가지고 DP를 추가로 사용해야한다는 것을 적어놓은 것을 찾았다.

• 이 문제의 경우 도착이라는 개념이 없기 때문에 시간초과를 조심해야한다.

https://loosie.tistory.com/250

단순 DFS 만으로는 불가능

4 ^(50 x 50) 번 최대 반복하기 때문에 시간초과 가능

그래서 DP를 추가로 생각해야한다고 한다.

알고리즘

• DFS,DP

CODE

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

public class Main {

    static int n,m;
    static int hole = -999;

    static int max = Integer.MIN_VALUE;

    //무한루프인지 체크용도
    static boolean flag = false;

    static int [][] dp,map;

    static boolean visited[][];


    static int dx[] = {-1,1,0,0};
    static int dy[] ={0,0,-1,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());

        map = new int[n][m];
        dp = new int[n][m];
        visited = new boolean[n][m];


        for(int row = 0; row <n;row++){
            String line = br.readLine();
            for(int col = 0; col<m;col++){
                if(line.charAt(col) == 'H'){
                    map[row][col] = hole;
                }else{
                    map[row][col] = line.charAt(col) -'0';
                }
            }
        }

        visited[0][0] = true;
        dfs(0,0,1);

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

    }

    private static void dfs(int x, int y, int cnt) {
        if(max < cnt){
            max = cnt;
        }
        dp[x][y] = cnt;

        for(int idx = 0; idx <4;idx++){
            int move = map[x][y];
            int nx = x + (move*dx[idx]);
            int ny = y + (move*dy[idx]);
            
            //맵을 벗어나거나 목적지가 hole인경우 out
            if(nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == hole){
                continue;
            }

            //이미 온적있는곳을 다시오는 경우 무한루프가 돈다.
            if(visited[nx][ny]){
                flag = true;
                return;
            }

            //이미 탐색한 부분은 스킵한다.
            if(dp[nx][ny] > cnt) continue;

            visited[nx][ny] = true;
            dfs(nx,ny,cnt+1);
            visited[nx][ny] = false;


        }
    }
}