BOJ 17090 미로 탈출하기

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

문제

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.

어떤 칸(r, c)에 적힌 문자가

• U인 경우에는 (r-1, c)로 이동해야 한다.
• R인 경우에는 (r, c+1)로 이동해야 한다.
• D인 경우에는 (r+1, c)로 이동해야 한다.
• L인 경우에는 (r, c-1)로 이동해야 한다.

미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

---

입력

첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

---

출력

첫째 줄에 탈출 가능한 칸의 수를 출력한다.

---

예제 입력 1

3 3
DDD
DDD
DDD

예제 출력 1

9

예제 입력 2

3 3
DDR
DLU
LLL

예제 출력 2

9

… 이하 예제 생략

---

코드

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

public class Main {
    static int N, M, answer = 0;
    static int[][] map;
    static boolean[][] visited;
    static int[] dirRow = {-1, 0, 0, 1}, dirCol = {0, 1, -1, 0};

    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];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                switch (br.read()) {
                    case 'U': map[i][j] = 0; break;
                    case 'R': map[i][j] = 1; break;
                    case 'L': map[i][j] = 2; break;
                    case 'D': map[i][j] = 3; break;
                }
            }
            br.readLine();
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                checkEscapable(i, j);
            }
        }
        System.out.println(answer);
    }
    
    static void checkEscapable(int row, int col) {
        // 검사하는 블록이 이미 탈출 가능하다고 증명된 경우, 증명하지 않고 answer++
        if (map[row][col] == Integer.MAX_VALUE) {
            answer++;
            return;
        }
        
        // 검사하는 블록이 이미 탈출 불가능하다고 증명된 경우, 증명하지 않고 검사 종료
        if (map[row][col] == Integer.MIN_VALUE) return;
        
        // dfs로 탈출 가능 여부 검사
        dfs(row, col);
    }

    static boolean dfs(int row, int col) {
        visited[row][col] = true; // 무한루프에 빠지지 않기 위해 visited 체크
        // 검사 위치의 알파벳에 따라 이동할 위치 계산
        int newRow = row + dirRow[map[row][col]], newCol = col + dirCol[map[row][col]];
        // 이동할 위치가 탈출인(맵 밖인) 여부 조사
        boolean isEscaped = newRow < 0 || newRow >= N || newCol < 0 || newCol >= M;
        boolean result;
        // 이동할 위치가 탈출이거나 이미 탈출 가능하다고 증명된 경우,
        // 이동할 위치가 무한루프에 빠지는 위치거나 이미 탈출 불가능하다고 증명된 경우,
        // 이동할 위치의 탈출 가능 여부가 아직 검사되지 않은 경우로 나눠서 해결한다.
        if (isEscaped || map[newRow][newCol] == Integer.MAX_VALUE) {
            answer++;
            result = true;
        } else if (visited[newRow][newCol] || map[newRow][newCol] == Integer.MIN_VALUE) {
            result = false;
        } else {
            result = dfs(newRow, newCol);
        }
        if(result) map[row][col] = Integer.MAX_VALUE; // 검사 위치가 탈출 가능한 경우 해당 위치를 MAX_VALUE로 초기화
        else map[row][col] = Integer.MIN_VALUE; // 검사 위치가 탈출 불가능한 경우 해당 위치를 MIN_VALUE로 초기화
        return result; // 검사 결과를 반환해 이전 위치의 검사 결과를 알림
    }
}