[백준]2178 미로탐색

2178 미로탐색

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Algorithm {
    public static int[][] matrix = null;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};
    public static int[][] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        matrix = new int[n][m];
        visited = new int[n][m];

        for(int i=0;i<matrix.length;i++){
            arr = br.readLine().split("");

            for(int j=0;j<matrix[i].length;j++){
                matrix[i][j] = Integer.parseInt(arr[j]);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        queue.offer(0);
        visited[0][0] = 1;

        while(!queue.isEmpty()){
            int x = queue.poll();
            int y = queue.poll();

            for(int i=0;i<4;i++){
                int newX = x + dx[i];
                int newY = y + dy[i];

                if(newX >= 0 && newY >= 0 && newX < matrix.length && newY < matrix[0].length && visited[newX][newY] == 0 && matrix[newX][newY] == 1){
                    queue.offer(newX);
                    queue.offer(newY);
                    visited[newX][newY] = visited[x][y] + 1;
                }
            }
        }

        for(int i=0;i<visited.length;i++){
            System.out.println(Arrays.toString(visited[i]));
        }

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

    }

}

bfs를 사용하여 거리를 측정한다