[JAVA]백준2178번 미로탐색

문제는 다음과 같다.

오늘은 백준2178번 미로탐색 문제를 풀어보도록 하자. JAVA에 익숙해지기 위해서 푼 기본적인 BFS or DFS문제이다. 0,0 에서 시작하여 N-1,M-1 까지 가는데 가장 짧은 거리를 구하는 문제이다.

                                     [코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class pos{
    int y;
    int x;
    int cnt;
    pos(int y, int x, int cnt) {
        this.y = y;
        this.x = x;
        this.cnt = cnt;
    }
}


public class Main {
    static int N,M,answer = 1;
    static boolean visit[][];
    static char map[][];
    static int dir[][] = { {-1,0},{0,1},{1,0},{0,-1} };

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visit = new boolean[N][M];
        map = new char[N][M];

        for(int i=0;i<N;i++){
            String s = br.readLine();
            map[i] = s.toCharArray();
        }
        visit[0][0] = true;
        bfs(0,0);
        System.out.println(answer);
    }

    static public void bfs(int y, int x){
        Queue<pos> Q = new LinkedList<pos>();
        Q.offer(new pos(y,x,1));

        while(!Q.isEmpty()){
            int ny = Q.peek().y;
            int nx = Q.peek().x;
            int cnt = Q.peek().cnt;

            Q.poll();

            if(ny == N-1 && nx == M-1){
                answer = cnt;
                return;
            }

            for(int i=0;i<4;i++){
                int my = ny + dir[i][0];
                int mx = nx + dir[i][1];

                if(my>=0 && mx>=0 && my<N && mx<M){
                    if(map[my][mx] == '1' && !visit[my][mx]){
                        visit[my][mx] = true;
                        Q.offer(new pos(my,mx,cnt+1));
                    }
                }
            }
        }
    }
}