미로 탈출하기

📍 문제 설명

 

💡 접근

단순하게 방문했던 곳을 방문했을 경우만 처리를 해주면 시간초과가 나는 문제였다.

각 좌표에서 문자에 따라 방문할 때 해당 좌표를 거쳐간 경로가 탈출 가능 경로인지 불가능 경로인지를 입력해두면 다른 좌표에서 방문할 때 거쳤던 경로의 탈출 가능 여부에 따라 바로 리턴시켜줄 수 있으므로 효율적으로 탐색이 가능해진다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer, cnt, max, min, wall, result = Integer.MAX_VALUE;
    static char[][] board, clone, dis;
    static boolean[][] visited,successRoute;
    static int[] parent = new int[100001];
    static int[] ch,pm, combi;
    static boolean flag = false;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        kb.nextLine();
        board = new char[n][m];
        visited = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            String s = kb.nextLine();
            for(int j = 0; j < m; j++) {
                board[i][j] = s.charAt(j);
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(T.solution(i, j)) cnt++;
            }
        }
        System.out.println(cnt);
    }

    private boolean solution(int x, int y) {
        boolean result = false;
        //해당 좌표에서 탈출 가능한지 확인
        if(x < 0 || y < 0 || x >= n || y >= m) {
            return true;
        }
        //갈 수 있던 곳이면 갈 수 있다.
        if(board[x][y] == 'T') return true;
        //갈 수 없었던 곳이면 갈 수 없다.
        else if(board[x][y] == 'F') return false;

        //방문한 곳을 또 가면 못나가는거야
        if(visited[x][y]) return false;

        visited[x][y] = true;
        //방문한 곳은 T or F 처리가 될꺼니까 방문 해제해서 다시 방문할 필요 없음
        if(board[x][y] == 'U') result = solution(x-1, y);
        if(board[x][y] == 'R') result = solution(x, y+1);
        if(board[x][y] == 'D') result = solution(x+1, y);
        if(board[x][y] == 'L') result = solution(x, y-1);

        board[x][y] = result? 'T' : 'F';
        return result;
    }
}