[Algorithm] 미로 탈출

문제

동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오.

 

입력 조건

첫째 줄에는 N과 M이 주어진다.

두번째 줄부터 미로에 대한 정보가 주어진다.

 

출력 조건

최소 이동 칸의 개수를 출력한다.

 

풀이

미로를 탈출하는데 움직여야 하는 최소 칸의 개수를 구한다. 현재 위치에서 근처에 있는 칸부터 탐색하며 이동하면서 가야 한다. BFS (너비 우선 탐색)을 이용해 주변을 탐색하면서 이동하도록 하면 될 것 같다.

 

import java.util.*;

class Block {
  private int x, y;

  Block (int x, int y) {
    this.x = x;
    this.y = y;
  }

  public int getX() {
    return this.x;
  }

  public int getY() {
    return this.y;
  }
} // end class Block

class Main {

  public static int[][] map;
  public static int n;
  public static int m;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();

    map = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        map[i][j] = sc.nextInt();
      }
    }
    sc.close();

    // (0,0)에서 (n-1,m-1)까지 이동하면서 움직인 칸의 개수
    
    Queue<Block> q = new LinkedList<>();
    int x = 0, y = 0;
    q.offer(new Block(x, y));
    
    int[][] direction = {
      {0, -1}, {0, 1}, {-1, 0}, {1, 0}
    };

    while (!q.isEmpty()) {
      Block block = q.poll();
      x = block.getX();
      y = block.getY();
      for (int i = 0; i < 4; i++) {
        int dx = direction[i][0] + x;
        int dy = direction[i][1] + y;
        if ((dx < 0 || dx >= n) || (dy < 0 || dy >= m)) continue;
        if (map[dx][dy] == 0) continue;
        if (map[dx][dy] == 1) {
          map[dx][dy] += map[x][y]; //움직이면서 합
          q.offer(new Block(dx, dy));
        }
      }
    }

    System.out.println(map[n-1][m-1]);
  } // end main
}