[BOJ] 14923. 미로 탈출(BFS).java

#. Problem

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

* 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

"가장 빠른 경로의 거리"를 구하기 위해 BFS가 적합하다.

2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000

시간복잡도는 O(N*M)로 충분하다.

신경 써 줄 부분은 마법의 지팡이를 단 한 번만 사용하여 벽을 부술 수 있다.

지팡이를 사용하지 않았을 경우와 한 번 사용했을 경우 체크를 따로 해주어야 한다.

간단히 살펴보면, 특정 좌표에서

1. 지팡이를 사용하지 않고 방문을 했을 경우

2. 지팡이를 한 번 사용하고 방문했을 경우

는 완전히 다른 경우이다.

그러므로 두 경우를 분리해서 생각해주어야 한다.

visit 상태 배열은 

[지팡이를 사용한 횟수][행][열]로 사용되어야 한다.

#. 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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ14923 {       static int N, M, Hx, Hy, Ex, Ey;     static int[][] map;     static int[] dr = {0, 1, 0, -1}, dc = {-1, 0, 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];                  // 홍익이 위치         st = new StringTokenizer(br.readLine());         Hx = Integer.parseInt(st.nextToken()) - 1;         Hy = Integer.parseInt(st.nextToken()) - 1;         // 탈출 위치         st = new StringTokenizer(br.readLine());         Ex = Integer.parseInt(st.nextToken()) - 1;         Ey = Integer.parseInt(st.nextToken()) - 1;                  for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());             for (int j = 0; j < M; j++) {                 map[i][j] = Integer.parseInt(st.nextToken());              }         }                  System.out.println(process());     }       private static int process() {                  int time = 0;         // [지팡이를 사용한 횟수][세로][가로]         boolean[][][] visited = new boolean[2][N][M];         Queue<Hong> q = new LinkedList<>();                  q.add(new Hong(Hx, Hy, 0));         visited[0][Hx][Hy] = true;                  while(!q.isEmpty()) {                          ++time;             int size = q.size();             while(size-- > 0) {                                  Hong now = q.poll();                 // 4방탐색                 for (int d = 0; d < 4; d++) {                     int rr = now.r + dr[d];                     int cc = now.c + dc[d];                                          // 범위를 벗어날 경우                     if(rr < 0 || cc < 0 || rr >= N || cc >= M) continue;                                          // 벽이라면                     if(map[rr][cc] == 1) {                         // 지팡이를 사용할 수 있고 방문하지 않았을 경우                         if(now.cnt == 0 && !visited[now.cnt + 1][rr][cc]) {                             // 이동할 곳이 탈출 위치라면                             if(rr == Ex && cc == Ey) return time;                                                          q.add(new Hong(rr, cc, now.cnt + 1));                             visited[now.cnt + 1][rr][cc] = true;                         }                      }                     // 벽이 아닐 경우                     else {                         // 방문하지 않았을 경우                         if(!visited[now.cnt][rr][cc]) {                             // 이동할 곳이 탈출 위치라면                             if(rr == Ex && cc == Ey) return time;                                                          q.add(new Hong(rr, cc, now.cnt));                             visited[now.cnt][rr][cc] = true;                         }                     }                 }             }         }                  // 탈출 할 수 없다면         return -1;     }       static class Hong {         int r, c, cnt;           public Hong(int r, int c, int cnt) {             this.r = r;             this.c = c;             this.cnt = cnt;         }              } }   Colored by Color Scripter

cs