2178 미로 탐색 (JAVA)

• 최단거리 문제이기 때문에 BFS 적용
• dx, dy배열을 이용하여 행렬의 상하좌우를 탐색
• Queue에 정수 두개를 어떻게 넣을까?? 고민하다가 정수 두개 멤버변수로 갖는 Point class로 해결

import java.util.*;
public class Main {

	// 가로, 세로를 갖는 클래스
    static class Point{
        int hei;
        int wid;
        public Point(int hei, int wid) {
            this.wid = wid;
            this.hei = hei;
        }
    }

    static int w,h;
    static int[][] graph;
    static boolean[][] ch;
    
    // 상하 좌우 탐색용
    static int[] dx = {-1,0,0,1};
    static int[] dy = {0,1,-1,0};
    
    // BFS
    static int BFS(int hei, int wid){
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(hei, wid));
        int L = 1;
        while(!q.isEmpty()){
            int len = q.size();
            for(int i=0; i<len; ++i){
                Point v = q.poll();
                if(v.wid == w-1 && v.hei == h-1)
                    return L;
                for(int j=0; j<dx.length; ++j){
                    int vh = v.hei + dy[j];
                    int vw = v.wid + dx[j];
                    if(vw >= 0 && vh >= 0
                        && vw < w && vh < h
                            && !ch[vh][vw] && graph[vh][vw]==1){
                        ch[vh][vw] = true;
                        // Queue에 다음 정점을 Point 객체로 넘김
                        q.offer(new Point(vh, vw));
                    }
                }
            }
            L++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        h = sc.nextInt();
        w = sc.nextInt();
        graph = new int[h][w];
        ch = new boolean[h][w];

        for (int i = 0; i < h; ++i) {
            String input = sc.next();
            for (int j = 0; j < w; ++j)
                graph[i][j] = input.charAt(j)-'0';
        }
        // 첫좌표를 체크하고 BFS 시작
        ch[0][0] = true;
        System.out.println(BFS(0,0));

    }
}