BOJ 2178 - 미로 탐색(BFS)

www.acmicpc.net/problem/2178

2178번: 미로 탐색

미로탐색 문제는 (1,1) ~ (N,M)까지의 최소 거리를 구하는 문제입니다.

이런 연결되어 있는 배열을 탐색해 나가야 하는 상황에서는 BFS를 사용하고 첫번 째 칸에 1을 대입하고 나머지 칸에 +1을 해나가면서 거리를 확장시켜 나가면서 풀어야 합니다.

코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class boj2178 {

    static int[][] board;
    static int[][] dist;
    static int N, M;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        board = new int[N][M];
        dist = new int[N][M];
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < M; j++) {
                board[i][j] = (int)str.charAt(j)- 48;
                dist[i][j] = -1;
            }
        }

        Pair pair = new Pair(0,0);
        dist[0][0] = 1;
        Queue<Pair> queue = new LinkedList();
        queue.add(pair);
        while(!queue.isEmpty()){
            Pair cur = queue.poll();
            for(int dir=0; dir<4; dir++){
                int nx = cur.r + dx[dir];
                int ny = cur.c + dy[dir];
                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if(dist[nx][ny] != -1 || board[nx][ny] == 0) continue;
                dist[nx][ny] = dist[cur.r][cur.c] + 1;
                queue.add(new Pair(nx,ny));
            }

        }

        System.out.println(dist[N-1][M-1]);

    }

    public static class Pair{
        int r;
        int c;

        Pair(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
}