[문제풀이] P159993 미로탈출

미로 탈출 / 구현문제 🚀

---

  🪅. BFS를 'Queue'를 이용하여 구현할 줄 알아야 한다.
         => 구현하면서 문제의 조건을 잘 따져서 넣어주어야 한다.
  🪅. String의 내장 메서드 '.toCharArray()'를 사용하면 편리하다.
  🪅. BFS의 '깊이(or Level)'를 구할 줄 알아야 한다. => queue의 'size()'와 'for문' 이용

  import java.util.*;
  class Solution {
      char[][] gMaps;
      int cnt;
      int[] dx = {-1, 0, 1, 0};
      int[] dy = {0, 1, 0, -1};
      int flag = 0;

      public void calExitDist(int[] start) {
          int row = gMaps.length;
          int col = gMaps[0].length;

          boolean[][] isVisited = new boolean[row][col];

          Queue<int[]> queue = new ArrayDeque<>();
          isVisited[start[0]][start[1]] = true;
          queue.offer(start);

          while(!queue.isEmpty()) {
              int len = queue.size();
              for(int t = 0; t < len; t++) {
                  int[] cur = queue.remove();
                  int x = cur[0];
                  int y = cur[1];
                  // System.out.println("x: " + x + " y: " + y);
                  for(int i = 0; i < 4; i++) {
                      int nx = x + dx[i];
                      int ny = y + dy[i];
                      if(nx < 0 || ny < 0 || nx >= row || ny >= col) continue;
                      if(isVisited[nx][ny]) continue;
                      if(gMaps[nx][ny] == 'O' || gMaps[nx][ny] == 'S') {
                          isVisited[nx][ny] = true;
                          queue.offer(new int[]{nx, ny});
                          // System.out.println("nx: " + nx + " ny: " + ny);
                      } else if(gMaps[nx][ny] == 'X') {
                          continue;
                      } else if(gMaps[nx][ny] == 'E') {
                          flag = 1;
                          cnt++;
                          return;
                      }
                  }
              }
              cnt++;
          }

          return;
      }
      public int[] calLeverDist(int[] start) {
          int row = gMaps.length;
          int col = gMaps[0].length;

          boolean[][] isVisited = new boolean[row][col];

          Queue<int[]> queue = new ArrayDeque<>();
          isVisited[start[0]][start[1]] = true;
          queue.offer(start);

          while(!queue.isEmpty()) {
              int len = queue.size();
              for(int t = 0; t < len; t++) {
                  int[] cur = queue.remove();
                  int x = cur[0];
                  int y = cur[1];
                  for(int i = 0; i < 4; i++) {
                      int nx = x + dx[i];
                      int ny = y + dy[i];
                      if(nx < 0 || ny < 0 || nx >= row || ny >= col) continue;
                      if(isVisited[nx][ny]) continue;
                      if(gMaps[nx][ny] == 'O' || gMaps[nx][ny] == 'E') {
                          isVisited[nx][ny] = true;
                          queue.offer(new int[]{nx, ny});
                      } else if(gMaps[nx][ny] == 'X') {
                          continue;
                      } else if(gMaps[nx][ny] == 'L') {
                          cnt++;
                          // System.out.println("nx: " + nx + " ny: " + ny);
                          return new int[]{nx, ny};
                      }
                  }
              }
              cnt++;
              // break;
          }
          // System.out.println("cnt: " + cnt);
          return new int[]{-1, -1};
      }

      public int[] findStart(String[] maps) {
          int i = 0;
          for(String row : maps) {
              char[] rowArr = row.toCharArray();
              // System.out.println(Arrays.toString(rowArr));
              for(int j = 0; j < rowArr.length; j++) {
                  if(rowArr[j] == 'S') { 
                      return new int[]{i, j};
                  }
              }
              i++;
          }
          return new int[]{};
      }
      public int solution(String[] maps) {
          int answer = 0;
          gMaps = new char[maps.length][maps[0].length()];
          for(int i = 0; i < maps.length; i++) {
              for(int j = 0; j < maps[0].length(); j++) {
                  gMaps[i][j] = maps[i].charAt(j);
              }
          }
          // for(int i = 0; i < gMaps.length; i++) {
          //     System.out.println(Arrays.toString(gMaps[i]));
          // }   

          int[] start = findStart(maps);

          int[] cur = calLeverDist(start);
          if(cur[0] == -1) return -1;
          calExitDist(cur);
          if(flag == 0) return -1;
          // System.out.println("shortest: " + cnt);
          return cnt;
      }
  }

💡.문제 접근 방법
: 최단시간(경로)을 구하라는 말에 가까운 노드부터 탐색하여, 최단시간을 보장하는 'BFS'가 생각났다.
단, 레버를 당기고 EXIT로 가라는 문제의 조건에 따라,
'START ~ 레버'까지의 최단경로와 '레버 ~ EXIT'로의 최단경로로 나누어 풀어야겠다는 생각을 했다.
문제의 조건에 지났던 경로를 또 지나도 된다는 조건때문에 잠시 헷갈렸는데,
최단 경로를 구할때는 isVisited 방문배열은 필수다.
문제의 조건을 꼼꼼히 신경쓰며 BFS를 구현하면, 무난하게 풀 수 있다.
다만, 최단경로를 나눠 푸는 과정에서 중복코드가 많이 들어가는데, 더 나은 방법이 있을 듯 하다.