[알고리즘 문제 풀이] 백준2178 미로탐색 (자바) : BFS

문제 설명

❝문제❞

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

❝ 입력 ❞

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

❝ 출력 ❞

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

❝ 출력 ❞

풀이 코드 

import java.awt.*;
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 Main{

    static int n,m;
    static int[][] arr;
    static boolean[][] visited;

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 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());

        arr = new int[n][m];
        visited = new boolean[n][m];

        //입력받기
        for(int i = 0; i < n; i++){
            String str = br.readLine();
            for(int j = 0; j<m; j++){
                arr[i][j] = str.charAt(j) - '0';
            }
        }

        search(0,0);

        System.out.println(arr[n-1][m-1]);

    }
    //현재 위치를 받아서
    public static void search(int x, int y){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x,y));
        visited[x][y] = true;

        while(!q.isEmpty()){
            Point current = q.poll();
            for(int i = 0; i<4; i++){
                int next_x = current.x + dx[i];
                int next_y = current.y + dy[i];

                if(next_x < 0 || next_x >= n ||next_y<0 || next_y >= m)
                    continue;
                if(visited[next_x][next_y]||arr[next_x][next_y]== 0)
                    continue;
                q.add(new Point(next_x, next_y));
                arr[next_x][next_y] = arr[current.x][current.y] + 1;
                visited[next_x][next_y] = true;
            }
        }

    }

}