BFS/미로 탈출 백준 14923번

알고리즘 : BFS

문제

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

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

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

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

 

입력

N M
Hx Hy
Ex Ey
N X M 행렬

• 2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000
• 1 ≤ Hx, Hy, Ex, Ey ≤ 1000
• (Hx, Hy)≠ (Ex, Ey)
• 행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

 

출력

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

 

예제 입력 1

5 6
1 1
5 6
0 1 1 1 0 0
0 1 1 0 0 0
0 1 0 0 1 0
0 1 0 0 1 0
0 0 0 1 1 0

 

예제 출력 2

11

 

힌트

제일 왼쪽 위 위치에서 제일 오른쪽 아래 위치로 이동하려면 (3,2) 벽을 파괴하고 이동하면 된다.

 

 

---

주의사항

- 방문 여부를 체크 함에 있어 마법의 지팡이를 사용했는지 여부도 포함시켜야 한다.

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

public class Main {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    
    private static int answer = -1;
    
    public static class Node {
        private int x;
        private int y;
        private int d;
        private boolean force;
        
        public Node(int x, int y, int d, boolean force) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.force = force;
        }
        public int getX() {
            return this.x;
        }
        public int getY() {
            return this.y;
        }
        public int getD() {
            return this.d;
        }
        public boolean getForce() {
            return this.force;
        }
        
    }
    
    public static boolean[][][] visited;
    public static int[][] mapInfo;
    
    public static int targetX;
    public static int targetY;
    
    public static int N;
    public static int M;
    
    public static int sX;
    public static int sY;
    
    public static boolean check(int x, int y) {
        if(x > 0 && y > 0 && x <= N && y <= M) return true;
        return false;
    }
    
    public static void bfs(Node start) {
        Queue<Node> q = new LinkedList<>();
        q.offer(start);
        visited[start.getX()][start.getY()][start.getForce() ? 1 : 0] = true;
        while(!q.isEmpty()) {
            Node cur = q.poll();
            if(cur.getX() == targetX && cur.getY() == targetY) {
                answer = cur.getD();
                break;
            }
           
            for(int i=0;i<4;i++) {
                int nextX = cur.getX() + dx[i];
                int nextY = cur.getY() + dy[i];
                if(check(nextX, nextY) && !visited[nextX][nextY][cur.getForce() ? 1 : 0]) {
                    if(mapInfo[nextX][nextY] == 0) { // 벽이 아닌 경우.
                        Node next = new Node(nextX, nextY, cur.getD()+1, cur.getForce());
                        q.offer(next);
                        visited[nextX][nextY][cur.getForce() ? 1 : 0] = true;
                    } else { // 벽인 경우.
                        if(!cur.getForce()) {
                           Node next = new Node(nextX, nextY, cur.getD()+1, true);
                           q.offer(next);
                           visited[nextX][nextY][1] = true; 
                        }
                    }
                }
            }
        }
    }
    
    public static void main(String args[]) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      
      mapInfo = new int[N+1][M+1];
      visited = new boolean[N+1][M+1][2];
      
      st = new StringTokenizer(br.readLine());
      
      sX = Integer.parseInt(st.nextToken());
      sY = Integer.parseInt(st.nextToken());
      
      st = new StringTokenizer(br.readLine());
      
      targetX = Integer.parseInt(st.nextToken());
      targetY = Integer.parseInt(st.nextToken());
      
      for(int i=1; i<=N; i++) {
          st = new StringTokenizer(br.readLine());
          for(int j=1; j<=M; j++) {
              mapInfo[i][j] = Integer.parseInt(st.nextToken());
          }
      }
      
      Node start;
      
      if(mapInfo[sX][sY] == 0) {
         start = new Node(sX, sY, 0, false);
      } else {
         start = new Node(sX, sY, 0, true);
      }
      
      bfs(start);
      
      System.out.println(answer);
    }
}

 

참고

- BFS : https://www.youtube.com/watch?v=CJiF-muKz30&t=197s

- 백준 14923 : https://www.acmicpc.net/problem/14923