[백준 - 14923번] 미로 탈출 - Java

문제 링크

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

문제

티어: 골드 4*
알고리즘: 그래프, bfs**
홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

입력

출력

D (탈출 할 수 없다면, -1을 출력한다.)

풀이

가장 빠른 경로의 거리 D를 구해야 한다.

D를 구하기 위해서는 3차 visited가 필요하다.

왜냐하면 두 가지 상태가 존재하기 때문이다.

1. 벽을 부시지 않은 상태 -> 0
2. 벽을 부신 상태 -> 1

그래서 0일 때 exit까지 이동 횟수와
1일 때 exit까지 이동 횟수를 비교해서 더 작은 값을 출력하면 된다.

만약 1일 때 exit까지 도달하지 못했다면 벽을 부수고도 탈출하지 못했기 때문에 -1를 출력한다.

이 풀이의 시간 복잡도는 O(N * M)이다.

소스 코드

import java.io.*;
import java.util.*;

class Location {
    int x, y, wl, c; //wl -> 0 안부심, wl -> 1 부심
    Location(int x, int y, int wl, int c) {
        this.x = x;
        this.y = y;
        this.wl = wl;
        this.c = c;
    }
}

public class Main {
    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, -1, 0, 1};
    static int N,M;
    
  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());
      int[][] map = new int[N][M];
      StringTokenizer st2 = new StringTokenizer(br.readLine());
      int hy = Integer.parseInt(st2.nextToken()) - 1;
      int hx = Integer.parseInt(st2.nextToken()) - 1;
      Location hong = new Location(hx, hy, 0, 1);
      StringTokenizer st3 = new StringTokenizer(br.readLine());
      int ey = Integer.parseInt(st3.nextToken()) - 1;
      int ex = Integer.parseInt(st3.nextToken()) - 1;
      Location exit = new Location(ex, ey, 0, 0);
      
      for(int i=0; i<N; i++) {
          StringTokenizer st4 = new StringTokenizer(br.readLine());
          for(int j=0; j<M; j++) {
              map[i][j] = Integer.parseInt(st4.nextToken());
          }
      }
      System.out.println(bfs(map, hong, exit));
  }
  
  
  static int bfs(int[][] map, Location hong, Location exit) {
      Queue<Location> que = new LinkedList<>();
      boolean[][][] visited = new boolean[2][N][M];
      que.add(hong);
      int result = Integer.MAX_VALUE;
      while(!que.isEmpty()) {
          Location node = que.poll();
          if(node.x == exit.x && node.y == exit.y) {
              result = Math.min(result, node.c);
          }
          for(int i=0; i<4; i++) {
              int nx = node.x + dx[i];
              int ny = node.y + dy[i];
              if((0 <= nx && nx <= M - 1) && (0 <= ny && ny <= N - 1)) {
                  if(map[ny][nx] == 0) {
                      if(!visited[node.wl][ny][nx]) {
                          visited[node.wl][ny][nx] = true;
                          que.add(new Location(nx, ny, node.wl, node.c + 1));
                      }
                  } else {
                      //벽이라면
                      if(node.wl == 0 && !visited[1][ny][nx]) {
                          //부실 수 있음
                          visited[1][ny][nx] = true;
                          que.add(new Location(nx, ny, 1, node.c));
                      }
                  }
              }
          }
      }
      if(result == Integer.MAX_VALUE) {
          return -1;
      }
      return result;
  }
}