[백준] 17090번 : 미로 탈출하기

17090번: 미로 탈출하기

---

[DFS + 동적 프로그래밍]

동적 프로그래밍을 사용하지 않고 DFS만 가지고도 충분히 해결할 수 있는 문제이다. 하지만 메모제이션을 사용하지 않으면 N x M의 각 좌표에서 다른 정점을 타고 탈출할 수 있는지 여부를 확인하기 위해 다른 정점에서 방문했었던 정점을 똑같이 방문하고, 방문하고...

 

이러한 반복적인 방문을 해결하기 위해, 특정 정점에서 탈출할 수 있다면 탈출할 수 있다고 체크를 한다면, 그 정점을 다시 방문했을 때 '아 여기서는 탈출할 수 있구나' 생각하고 그 이전의 정점 또한 탈출할 수 있다고 판단할 수 있다.

 

방법은 다음과 같다. dp[ ][ ]라는 int 배열을 -1로 초기화 한다.

그리고 해당 정점을 방문하면 dp[i][j] = 0으로 설정한다.

각 칸에 적힌 문자를 따라 이동하다 보면 탈출할 수 있는 곳이 있다. 탈출 했다면 1을 반환한다.

다른 정점에서 DFS를 수행하다가 dp[i][j] != -1인 지점을 발견하면 dp[i][j]을 반환받는다.

 

-1 : 방문하지 않음

0 : 방문했으나 탈출 불가능

1 : 방문했으며 탈출 가능

 

모든 정점에 대해 DFS를 수행했으면 dp에는 1 또는 0이 채워져 있을 것이다. 이제 이 모든 칸에 대해 result에 더해주면 된다.

# Code </>

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

public class Main {

    static int n, m;
    static char[][] map = new char[501][501];
    static int[][] dp = new int[501][501];
    static int[] Y = {-1, 0, 1, 0}, X = {0, 1, 0, -1};

    static boolean isEscape(int y, int x){

        return (y < 1 || x < 1 || y > n || x > m);
    }

    static int DFS(int y, int x){

        if(!isEscape(y, x) && dp[y][x] != -1)
            return dp[y][x];

        if(isEscape(y, x))
            return 1;

        dp[y][x] = 0;
        int ny = -1, nx = -1;

        if(map[y][x] == 'U')      {ny = y+Y[0]; nx = x+X[0];}
        else if(map[y][x] == 'R') {ny = y+Y[1]; nx = x+X[1];}
        else if(map[y][x] == 'D') {ny = y+Y[2]; nx = x+X[2];}
        else if(map[y][x] == 'L') {ny = y+Y[3]; nx = x+X[3];}

        dp[y][x] += DFS(ny, nx);

        return dp[y][x];
    }

    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());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=m; j++) {
                map[i][j] = str[j - 1];
                dp[i][j] = -1;
            }
        }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(dp[i][j] == -1)
                    DFS(i, j);

        int result = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                result += dp[i][j];

        System.out.println(result);
    }
}