<Algorithm> 22. 1261번 알고스팟(벽1 부수기)

1. 1261번 알고스팟(벽1 부수기)

• Dequeue 와 우선순위 Queue 를 이용하여 풀 수 있다. -> 우선순위가 2가지 일경우에 Dequeue 사용

• 벽을 부수지 않는 경우를 먼저 탐색하여 방문하지 않은 곳을 방문한 뒤 벽을 부순 경우를 탐색한다. 

• import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayDeque;
  import java.util.StringTokenizer;
   
   
  public class Main {
      public static void main(String[] args) throws IOException {
          
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
          
          int M = Integer.parseInt(st.nextToken());
          int N = Integer.parseInt(st.nextToken());
          int[][] graph =new int[N][M];
          int[][] dist = new int[N][M]; // 벽 1을 부순 횟수
          
          for(int i = 0; i < N; i++){
              for(int j = 0; j < M; j++) {
                  dist[i][j] = -1;
              }
          }
                  
          for(int i = 0; i < N ; i++) {
              st = new StringTokenizer(br.readLine());
              String temp = st.nextToken();
              for(int j = 0; j < M; j++) {
                  graph[i][j] = temp.charAt(j) - '0';
              }
          }
          
          
          int[] dx = {0, 0, 1, -1};
          int[] dy = {1, -1, 0, 0};
          ArrayDeque<Location> aDeque = new ArrayDeque<>();
          
          dist[0][0] = 0;
          
          aDeque.add(new Location(0, 0));
          
          while(!aDeque.isEmpty()) {
              Location loc = aDeque.poll();
              int x = loc.x;
              int y = loc.y;
              
              for(int k = 0; k < 4; k++) {
                  int nx = x + dx[k];  // 상하좌우
                  int ny = y + dy[k];
              
                  if(nx >= 0 && ny >= 0 && nx < N && ny < M) {
                      if(dist[nx][ny] == -1) { // 방문하지 않았을때
                          if(graph[nx][ny] == 0) { 
                              dist[nx][ny] = dist[x][y];
                              aDeque.addFirst(new Location(nx, ny));
                              //우선순위를 두는것 !! 0은 벽 1을 부수지 않기 때문에 앞에 추가
                          }else {
                              dist[nx][ny] = dist[x][y] + 1;
                              aDeque.addLast(new Location(nx, ny));
                              //벽을 부쉇기 때문에 우선순위가 아래
                          }
                      }
                  }    
              }
          }
          
          
          System.out.println(dist[N-1][M-1]);
      
      }
   
  }
   
  class Location{
      int x;
      int y;
      public Location(int x, int y) {
          this.x = x;
          this.y = y;
      }
  }