[백준] 2178 미로탐색 | BFS

문제

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

출력

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

입력

4 6
101111
101010
101011
111011

출력

15

소스

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

public class Main {


    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        try {
            String[] nums = br.readLine().split(" ");
            int n = Integer.parseInt(nums[0]);
            int m = Integer.parseInt(nums[1]);
            int[][] board = new int[n][m];
            int[] dx = {1, 0, -1, 0};
            int[] dy = {0, 1, 0, -1};
            int[][] distance = new int[n][m];


            for (int i = 0; i < n; i++) {
                String[] temp = br.readLine().split("");
                for (int j = 0; j < m; j++) {
                    board[i][j] = Integer.parseInt(temp[j]);
                }
            }

            Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
            queue.add(new Pair(0, 0));
            distance[0][0] = 0; //해줘도 되고 안해줘도 되고

            while (!queue.isEmpty()) {
                Pair<Integer, Integer> cur = queue.peek();
                queue.poll();

                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];

                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (board[nx][ny] == 0 || distance[nx][ny] > 0) continue;
                    distance[nx][ny] = distance[cur.first][cur.second] + 1;
                    queue.add(new Pair(nx, ny));
                }
            }
            System.out.println(distance[n-1][m-1] + 1);

        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}

class Pair<I extends Integer, I1 extends Integer> {
    Integer first;
    Integer second;

    public Pair(Integer first, Integer second) {
        this.first = first;
        this.second = second;
    }

    public Integer first() {
        return first;
    }

    public Integer second() {
        return second;
    }
}

후기

BFS를 이용해서 시작점부터 거리를 변수에 저장해주면 된다. BFS중에서도 난이도가 쉬운 문제인데 이 같은 거리 문제는 DFS는 사용할 수 없다. 시작점이 하나라서 꽤 쉬운 난이도의 문제였던 것 같다.