백준 2178번: 미로 탐색

문제 출처: https://www.acmicpc.net/problem/2178

참고

BFS(Breadth-First Search): http://qlyh8.tistory.com/30?category=731166

BFS 문제: http://qlyh8.tistory.com/31?category=731166

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    private static int N, M;
    private static int[][] miro;
    private static boolean[][] visit;
    private static int[] dirX = {0, 1, 0, -1}; // X 좌표
    private static int[] dirY = {1, 0, -1, 0}; // Y 좌표
 
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        miro = new int[N][M];
        visit = new boolean[N][M];
 
        for(int i=0 ; i<N ; i++){
            String inputLine = reader.readLine();
            for(int j=0 ; j<M ; j++){
                miro[i][j] = inputLine.charAt(j)-'0'; // 붙어서 입력으로 주어짐
            }
        }
 
        bfs(new Position(0, 0, 1)); // (0,0) 부터 탐색, 1 카운트
    }
 
    private static void bfs(Position position){
        Queue<Position> queue = new LinkedList<>();
        queue.offer(position); // 방문한 좌표를 큐에 넣음
        visit[position.getN()][position.getM()] = true; // visit 갱신
 
        while(!queue.isEmpty()){
            Position front = queue.poll(); // 방문한 좌표
 
            if(front.getN() == N-1 && front.getM() == M-1){ // 도착 위치일 경우 끝냄
                System.out.println(front.count);
                return;
            }
 
            for(int i=0 ; i<4 ; i++){ // 방문한 좌표의 주변 4방향 탐색
                int newN = front.getN() + dirY[i];
                int newM = front.getM() + dirX[i];
 
                if((0 <= newN && newN < N) && (0 <= newM && newM < M)){ // 미로 범위 내
                    if(miro[newN][newM] == 1 && !visit[newN][newM]){ // 이동할 수 있는 칸이고 방문하지 않았을 경우
                        visit[newN][newM] = true; // vist 갱신
                        queue.offer(new Position(newN, newM, front.getCount()+1)); // 큐에 넣음
                    }
                }
            }
        }
    }
 
    public static class Position{
        int n, m, count;
 
        Position(int n, int m, int count) {
            this.n = n;
            this.m = m;
            this.count = count;
        }
 
        int getN(){return n;}
 
        int getM(){return m;}
 
        int getCount(){return count;}
    }
}