[BaekJoon] 17090 미로 탈출하기 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final Map<Character, int[]> DIRECTION = new HashMap<>() {{
        put('U', new int[]{-1, 0});
        put('R', new int[]{0, 1});
        put('D', new int[]{1, 0});
        put('L', new int[]{0, -1});
    }};

    static int rowLen;
    static int colLen;
    static char[][] map;
    static int[][] visited;
    static boolean[][] isVisited;

    static void input() {
        Reader scanner = new Reader();

        rowLen = scanner.nextInt();
        colLen = scanner.nextInt();
        map = new char[rowLen][colLen];
        visited = new int[rowLen][colLen];
        isVisited = new boolean[rowLen][colLen];

        for (int row = 0; row < rowLen; row++) {
            String info = scanner.nextLine();
            for (int col = 0; col < colLen; col++) {
                map[row][col] = info.charAt(col);
            }
        }
    }

    /*
     * 미로의 모든 지점에 대해 탈출 가능한 칸인지 dfs를 통해 확인한다
     *  - 시작 칸에서 dfs를 통해 각 칸에 적혀있는 문자에 따라 이동해보면서
     *      - 만약 미로의 경계 밖으로 이동하는 칸이 경로에 존재한다면 해당 경로에 있는 칸들은 모두 탈출 가능한 칸이기 때문에
     *        모든 칸들을 탈출 가능한 칸으로 설정한다
     *      - 만약 경로상에 존재하는 칸을 다시 방문하게 된다면 미로의 경계 밖으로 이동할 수 없는 경로이므로
     *        경로 상에 있는 모든 칸들을 탈출 불가능한 칸으로 설정한다
     *
     * 이때, 모든 지점을 탈출 가능한 칸인지 매번 dfs를 진행하면 시간 초과가 일어난다
     * 그러므로 이전에 dfs를 통해 방문한 칸들은 탈출 가능한 칸인지 결정이 된 칸들이기 때문에
     * 탈출 가능 여부를 저장해놓고 다시 해당 칸을 방문했을 때에는 해당 탈출 가능 여부를 이용한다
     */
    static void solution() {
        for (int row = 0; row < rowLen; row++) {
            for (int col = 0; col < colLen; col++) {
                if (visited[row][col] == 0) {
                    findPossibilityAboutEscape(row, col);
                }
            }
        }
        System.out.println(getPossibleSpace());
    }

    static int getPossibleSpace() {
        int answer = 0;
        for (int row = 0; row < rowLen; row++) {
            for (int col = 0; col < colLen; col++) {
                if (visited[row][col] == 1) {
                    answer++;
                }
            }
        }

        return answer;
    }

    static int findPossibilityAboutEscape(int row, int col) {
        int nextX = row + DIRECTION.get(map[row][col])[0];
        int nextY = col + DIRECTION.get(map[row][col])[1];
        if (!isInMap(nextX, nextY)) {
            return visited[row][col] = 1;
        }
        if (visited[row][col] != 0) {
            return visited[row][col];
        }
        if (isVisited[row][col]) {
            return visited[row][col] = -1;
        }

        isVisited[row][col] = true;
        return visited[row][col] = findPossibilityAboutEscape(nextX, nextY);
    }

    static boolean isInMap(int row, int col) {
        return row >= 0 && row < rowLen && col >= 0 && col < colLen;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}