[백준] 2178번 - 미로 탐색 - Java

 

BFS 를 이용해서 풀었습니다. 

미로판인 board 배열에 미로판 값을 입력받아 저장하고 미로판을 BFS 로 탐색하며 탐색한 위치까지의 이동 거리를

dis 배열에 저장합니다. 그리고 dis 배열에서 도착점의 좌표 값을 출력합니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class p2178 {
    static int N, M;
    //좌 상 우 하
    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};
    static int[][] board, dis;

    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());
        board = new int[N][M];
        dis = new int[N][M];

        for(int i=0; i<N; i++) {
            String s = br.readLine();

            for(int j=0; j<M; j++) {
                board[i][j] = Integer.parseInt(String.valueOf(s.charAt(j)));
            }
        }

        //출발점부터 BFS 시작
        BFS(0, 0);
        //도착점까지의 최소 경로값 출력
        System.out.println(dis[N-1][M-1] + 1);
    }

    public static void BFS(int x, int y){
        Queue<Point> Q = new LinkedList<>();

        //파라미터로 들어온 좌표 큐에 추가
        Q.offer(new Point(x, y));

        while(!Q.isEmpty()){

            //큐에서 빼낸 좌표
            Point tmp = Q.poll();

            //좌 상 우 하 탐색해 0인 좌표 찾음
            for(int i=0; i<4; i++){

                //이동하려는 좌표 설정
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];

                //이동하려는 좌표 경계 넘지 않지 않고 벽이 아니면
                if(nx>=0 && nx<N && ny>=0 && ny<M && board[nx][ny] == 1){
                    //해당 좌표로 이동하니 재방문하지 않게 벽으로 만들기
                    board[nx][ny] = 0;

                    //해당 좌표 큐에 추가
                    Q.offer(new Point(nx, ny));

                    //전 위치 값에 + 1 해서 이동한 위치의 값 설정
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
    }

    static class Point{

        public int x, y;

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