[BOJ] 백준 2178 미로 탐색

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

 Input 

4 6

110110

110110

111111

111101

 

 Output 

9

* input data는 각각의 수들이 붙어서 입력되므로 주의.

BFS 이용

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Vertex{
    int x, y;
    int count;
     
    public Vertex(int x, int y, int count) {
        this.x = x;
        this.y = y;
        this.count = count;
    }
}
 
public class Main {
    public static void main(String[] args) {
         
        Scanner sc = new Scanner(System.in);
         
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
        int[][] arr = new int[N+1][M+1];
        String[] str = new String[N];
         
        for(int i=0; i<N; i++) {
            str[i] = sc.next();
            for(int j=1; j<=M; j++) {
                arr[i+1][j] = Character.getNumericValue(str[i].charAt(j-1));
            }
        }
         
        Queue<Vertex> queue = new LinkedList<>();
         
        // 동(오른쪽), 서(왼쪽), 남(아래), 북(위)
        int[] rowMove = {0, 0, 1 , -1};
        int[] colMove = {1, -1, 0 ,0};
         
        // 이미 방문한 지점이면 '-1'로 표시
        arr[1][1] = -1;
         
        queue.add(new Vertex(1, 1, 1));
         
        while(!queue.isEmpty()) {
             
            Vertex cur_v = queue.poll();
            for(int i=0; i<4; i++) {
                // 다음 이동할 좌표
                int next_x = cur_v.x + rowMove[i];
                int next_y = cur_v.y + colMove[i];
                 
                // 배열 index를 (1,1)~(N,M)까지 중에서 탐색
                if(next_x > 0 && next_y > 0 && next_x <= N && next_y <= M ) {
                    // 최종 도착
                    // (항상 마지막에는 도착하도록 input data가 주어진다.)
                    if(next_x == N && next_y == M) {
                        System.out.println(cur_v.count+1);
                        return;
                    }
                    if(arr[next_x][next_y] == 1) { // 이동할 수 있는 지점 (방문하지 않은 지점이면서 이동가능한 길)
                        // 현재 이동되는 level, height, 출발점에서의 최단거리를 인스턴스 변수 'count'에 저장
                        queue.add(new Vertex(next_x, next_y, cur_v.count + 1));
                        arr[next_x][next_y] = -1; // 방문 표시
                    }
                }       
            }
        }
    }
}