백준 17090번: 미로 탈출하기 (Java)

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

17090번: 미로 탈출하기

 

 

 

 

 

 

 

 

---

 

풀이

각 위치에서 주어진 방향대로 이동해서 탈출할 수 있는지 구현해야 합니다. 다만, M=N=500(총 25만개의 칸)이고, 모든 칸의 경로가 하나로 연결되어 탈출하는 시나리오를 생각해봅시다. 이 경우, 각 칸에서 탈출할 수 있을 지 여부를 계산하는 횟수는 1, 2, 3, ... , 25만번인, O(M^2N^2) 시간 복잡도를 가져 시간초과가 발생하게 됩니다. 생각을 해보면, 연결된 경로는 사실 탈출 가능 여부가 동일하기에, 처음 방문 시기에 1)방문했음을 기록하고, 2)이후 해당 경로의 탈출 여부를 계산하여 갱신해줍니다. 그러면, 다음에 해당 위치에 방문하면 해당 위치의 탈출 여부가 기록되어있으므로, 중복된 연산을 할 필요가 없습니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static int[][] map;
    static int M, N;
    static boolean[][] visited, canEscape;
    static Map<String, Integer> dir = new HashMap<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        visited = new boolean[M][N]; // 해당 위치에서 탈출할 수 있는지 확인한 여부를 저장
        canEscape = new boolean[M][N]; // 해당 위치에서 탈출할 수 있는지 저장
        for (int i = 0; i < M; i++) {
            String row = br.readLine();
            for (int j = 0; j < N; j++) {
                // case-work
                char letter = row.charAt(j);
                switch (letter) {
                case 'U':
                    map[i][j] = 0;
                    break;
                case 'R':
                    map[i][j] = 3;
                    break;
                case 'D':
                    map[i][j] = 1;
                    break;
                case 'L':
                    map[i][j] = 2;
                    break;
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (dfs(i, j)) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
    
    // (r, c)에서 도망갈 수 있는지 계산하는 method
    static boolean dfs(int r, int c) {
        // 이미 방문했다면 canEscape에 탈출 가능 여부가 있음
        if (visited[r][c]) return canEscape[r][c];
        
        visited[r][c] = true;
        // 방향대로 이동
        int nr = r + dr[map[r][c]], nc = c + dc[map[r][c]];
        // 만약 지도 밖으로 나갔다면 탈출 가능
        if (!isIn(nr, nc)) return canEscape[r][c] = true;
        // (r, c)에서의 탈출 가능성은 (nr, nc)에서의 탈출 가능성과 동일
        return canEscape[r][c] = dfs(nr, nc);
    }
    
    static boolean isIn(int r, int c) {
        return !(r < 0 || r >= M || c < 0 || c >= N);
    }
}