2178-미로탐색

2178번: 미로 탐색

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

public class B2178 {
    static int N,M;
    static int[][] Board;
    static int[][] D = {{-1,0},{1,0},{0,-1},{0,1}}; //상 하 좌 우
    static boolean[][] visited;

    static class Node{
        int row, col, count;
        Node(int r, int c, int ct){
            row = r;
            col = c;
            count = ct;
        }
    }

    public static int move(){
        Queue<Node> queue = new LinkedList<>();
        visited = new boolean[N][M];
        visited[0][0] = true;
        //지나야하는 칸수를 구하라고 했으니 count에 1을 넣어준다
        queue.add(new Node(0,0,1));

        while(!queue.isEmpty()){
            Node temp = queue.remove();
            if(temp.row==N-1&&temp.col==M-1){
                return temp.count;
            }
            for(int i=0; i<4; i++){
            	// 현재 좌표에 상하좌우값을 각각 더해 검증
                int rd = temp.row + D[i][0];
                int cd = temp.col + D[i][1];

                if(rd<0||rd>=N||cd<0||cd>=M) continue;
                if(Board[rd][cd]==0) continue;
                if(visited[rd][cd]) continue;
                visited[rd][cd] = true;
                queue.add(new Node(rd,cd,temp.count+1));
            }
        }
        return -1;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        Board = new int[N][M];
        String str;
        //한줄로 숫자를 받아야 해서 string으로 받고 변환
        for(int i=0; i<N; i++) {
            str= sc.next();
            for(int j=0; j<M; j++) {
                Board[i][j]= Integer.parseInt(str.charAt(j)+"");
            }
        }
        System.out.println(move());
    }
}

 

이번문제는 지난번에 푼 최단거리 문제와 비슷해서 엄청 쉽게 풀었다