백준_Java_2178

• while문으로 큐가 비어있을 때까지 반복합니다.
• spot 인스턴스를 q에 있는 0,0으로 만들어 줍니다.
• 이제 큐에서 빼온 s를 동서남북으로 확인해 줍니다.
• 만약 범위가 주어진 범위보다 넘어가면 continue를 통해 다음 방향(동서남북)으로 전환해 줍니다.
• 만약 이미 방문했거나 해당 방향의 값이 0이라면 continue를 통해 다음 방향으로 전환해 줍니다.
• 이 모든 if문을 통과했다면, q에다가 해당 좌표를 추가해 줍니다. 그리고 해당 arr 값에 +1을 해줍니다.
• 또한 그 좌표를 방문했다는 의미인 check를 true로 바꿔줍니다.

대부분의 모든 미로 문제는 이러한 bfs를 통해 산출

import java.io.*;
import java.util.*;

public class Main {
    static int[][] arr;
    static boolean[][] visited ;
    // 가로 세로 연결 
    static int[] dirX = new int[]{0, 0, -1,1};
    static int[] dirY = new int[]{1, -1,0,0};
    //현재 위치 x, y
    static int nowX, nowY
    static int result;

    // 지도 밖에 못나가게 Range_Check
    // 방문 visited
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

        arr = new int[h + 1][w + 1];
        visited = new boolean[h + 1][w + 1];

        for (int i = 1; i <= h; i++) {
            String s = br.readLine();
            for (int j = 1; j <= w; j++) {
                arr[i][j] = s.charAt(j-1) - '0';
            }
        }
        BFS(1, 1);
        System.out.println(arr[h][w]);
    }

    static void BFS(int x, int y) {
        Queue<spot> que = new LinkedList<>();
        visited[x][y] = true;
        //상하좌우 que 다넣어주기
        que.add(new spot(x,y));

        while (!que.isEmpty()) {
            spot q = que.poll();

            for (int i = 0; i < 4; i++) {
                nowX = q.x + dirX[i];
                nowY = q.y + dirY[i];
                if (Range_Check(nowX, nowY) && !visited[nowX][nowY] && arr[nowX][nowY] == 1) {
                    que.add(new spot(nowX,nowY));
                    arr[nowX][nowY] = arr[q.x][q.y] +1;
                    visited[nowX][nowY]= true;
                }
            }
        }
    }

    static boolean Range_Check(int x, int y) {
       if (x >=0 && x < arr.length && y >= 0 && y<arr[0].length)
           return true;

       return false;
    }
//각 지점을 확인할 수 있는 CLASS를 하나 설정
    static class spot{
        int x;
        int y;

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

참조 : https://infodon.tistory.com/100