[BOJ] 미로 탈출하기(DFS + DP).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

보기에 단순해 보여서 단순하게 풀었다가 시간 초과를 맛본 문제다..

우선 미로의 크기는 (3 ≤ N, M ≤ 500)로 최대 2500칸이 될 수 있다.

단순하게 생각하면 모든 칸(500^2)에서 탈출을 시도할 텐데,

최악의 경우 특정 칸에서 출발해서 모든 칸을(500^2) 다 돌아봐야 하는 경우가 있을 것이다.

이 경우 시간 복잡도는 O(500^4)이 되어버린다...

무려 62,500,000,000 의 연산량이 나오므로 당연 시간 초과를 맛볼 수 있다.

시간 초과를 맛있게 먹었으니..

다시 아이디어를 생각해보자.

//

특정 칸에서 탈출을 시도하면 여러 칸을 지나가게 될 것이다.

만일 1 -> 3 -> 5 -> 7 번 칸을 지나 탈출에 성공했다면

1, 3, 5, 7번 칸은 모두 탈출 가능한 칸이 되므로 굳지 다시 확인하지 않아도 된다.

여기서 메모이제이션을 적용해볼 수 있다.

Map 크기의 배열에 해당 칸에서 탈출이 가능한지 불가능한지를 기록해두는 것이다.

이럴 경우, 탈출 경로를 따라가면서 이미 탈출 가능했던 칸을 만나면 더이상 확인할 필요가 없고,

반대로 탈출 불가능했던 칸을 만나도 더이상 확인할 필요가 없다.

#. Code

자세한 설명은 주석을 참고하면 충분할 것 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ17090 {       static int N, M, map[][], isPosb[][];     static int[] dr= {-1, 0, 1, 0}, dc = {0, 1, 0, -1};          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];         isPosb = new int[N][M]; // 1: 탈출 가능, -1: 탈출 불가능, 0: 미확인                  for (int i = 0; i < N; i++) {             char tmp[] = br.readLine().toCharArray();             for (int j = 0; j < M; j++) {                 char now = tmp[j];                 // 문자에 번호 지정                 if(now == 'U') map[i][j] = 0;                 else if(now == 'R') map[i][j] = 1;                 else if(now == 'D') map[i][j] = 2;                 else map[i][j] = 3;             }         }                  int res = 0;         for (int i = 0; i < N; i++) {             for (int j = 0; j < M; j++) {                 int tmp = process(i, j, map[i][j]);                 // 탈출 불가능한 칸(-1)일 경우 0으로                 res += tmp < 0 ? 0 : tmp;             }         }                  System.out.println(res);     }       private static int process(int r, int c, int dir) {           // 이동할 다음 칸을 기준으로         int rr = r + dr[dir];         int cc = c + dc[dir];                  // 범위를 벗어날 경우 탈출 성공 (DP에 1을 저장하고 return)         if(rr < 0 || cc < 0 || rr >= N || cc >= M) return isPosb[r][c] = 1;         // 이미 확인한 구역일 경우 (DP에 저장된 값을 return)         else if(isPosb[rr][cc] != 0) return isPosb[rr][cc];                  // 우선 불가능으로 체크         isPosb[r][c] = -1;                  // 다음 칸으로 이동 (탈출 가능할 경우 1 저장 후 return)         // 자기 자신으로 돌아오거나 탈출 불가능한 칸을 거치면 -1 저장 후 return)         return isPosb[r][c] = process(rr, cc, map[rr][cc]);     }   }   Colored by Color Scripter

cs