[백준] 2178. 미로 탐색

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

---

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int[][] arr;
    static boolean[][] visited;
    static int min;
    public static void main(String[] args) throws Exception{
        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';
            }
        }
        min = Integer.MAX_VALUE;
        visited[0][0] = true;

        bfs();
        System.out.println(min);
    }

    public static int[] dr = {-1, 1, 0, 0};
    public static int[] dc = {0, 0 ,-1, 1};
    public static class Direction {
        int r;
        int c;
        int count;
        public Direction(int r, int c, int count) {
            this.r = r;
            this.c = c;
            this.count = count;
        }
    }
    public static void bfs() {
        Queue<Direction> queue = new LinkedList<>();
        queue.add(new Direction(0, 0, 1));
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            Direction direction = queue.poll();
            if(direction.r == N - 1 && direction.c == M - 1) {
                if(direction.count < min) {
                    min = direction.count;
                }
            }

            for(int i = 0; i < 4; i++) {
                int nr = direction.r + dr[i];
                int nc = direction.c + dc[i];
                if(nr >= 0 && nc >= 0 && nr < N && nc < M && !visited[nr][nc] && arr[nr][nc] == 1) {
                    visited[nr][nc] = true;
                    queue.add(new Direction(nr, nc, direction.count + 1));
                }
            }
        }
    }
}

bfs 기초이다. visited배열을 이용해 방문했던부분은 다시 가지 않고 Direction 클래스를 만들어 좌표, 이동한 거리를 같이 가지고 다닌다.