[AJ/BFS] 미로찾기

문제

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 출력하는 프로그램을 작성하시오. 아래 그림에 대하여 S에서 E까지 가는 최단거리는 22이다.

입력

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다.

출력

(N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다.

예제 입력

10 10 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0

예제 출력

22

---

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int dx[] = { 0, 1, 0, -1 };
        int dy[] = { 1, 0, -1, 0 };
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int map[][] = new int[n][m];
        int count[][] = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                map[i][j] = sc.nextInt();
        Queue<node> q = new LinkedList();
        q.add(new node(n - 1, 0));
        count[n - 1][0] = 0;
        while(!q.isEmpty()) {
            node tmp = q.poll();
            for(int i=0;i<4;i++) {
                int a = tmp.x+dx[i];
                int b = tmp.y+dy[i];
                if(a>-1 && a<n && b>-1 && b<m && map[a][b] == 0) {
                    if(count[a][b]==0){
                        count[a][b] = count[tmp.x][tmp.y]+1;
                        q.add(new node(a,b));
                    }else 
                        count[a][b] = Math.min(count[tmp.x][tmp.y]+1,count[a][b]);
                        
                }
            }
        }
        System.out.print(count[0][m - 1]);
    }
    public static class node {
        int x, y;
        public node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}