[BOJ 백준] 17090 - 미로 탈출하기, Java(자바)

문제

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

17090번: 미로 탈출하기

풀이

dfs + dp로 풀이했다. delta 배열의 인덱스에 맞춰 map 배열을 초기화한다. 배열을 돌면서 아직 방문하지 않은 곳이면 칸에 적힌대로 이동하고, 탈출할 수 있으면 지나온 경로를 모두 true로, 탈출할 수 없으면 지나온 경로를 모두 false로 나타내면서 탈출 가능한 칸의 수를 카운팅한다.

코드

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

public class Main {
    static int N, M, answer;
    static int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int[][] map;
    static boolean[][] dp, visited;
    
    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        dp = new boolean[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String str = in.readLine();
            for (int j = 0; j < M; j++)
                map[i][j] = str.charAt(j) == 'U' ? 0 : str.charAt(j) == 'D' ? 1 : str.charAt(j) == 'L' ? 2 : 3;
        }
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    dfs(i, j);
                }
            }
        }
        System.out.println(answer);
    }
    
    static void dfs(int r, int c) {
        int dr = r + delta[map[r][c]][0];
        int dc = c + delta[map[r][c]][1];
        
        if (dr < 0 || dc < 0 || dr >= N || dc >= M || (visited[dr][dc] && dp[dr][dc])) {
            dp[r][c] = true;
            answer++;
            return;
        }
        if (visited[dr][dc]) {
            dp[r][c] = false;
            return;
        }
        
        visited[dr][dc] = true;
        dfs(dr, dc);
        dp[r][c] = dp[dr][dc];
        if (dp[r][c])
            answer++;
    }
}