[백준 2178번] 미로 탐색

문제 링크: 2178번 제목

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

 

최단거리를 찾으므로 BFS로 구현하는 것이 유리하며, 방문하는 새로운 칸에는 현재의 칸에 저장된 값보다 1만큼 큰 값을 저장한다.

코드에서는 이용하지 않았지만, maze 배열의 테두리를 0(이동할 수 없는 칸)으로 감싸게 되면 새로 이동할 칸이 maze를 벗어나지 않는지 체크할 필요가 없다.

 

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

public class Main {
    static class Pos {
        int row;
        int col;
        Pos(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    static int[][] maze;
    static boolean[][] visit;
    static int n;
    static int m;

    public static void main(String[] args) throws IOException {
        /* input */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] mn = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = mn[0];
        m = mn[1];
        maze = new int[n][m];
        visit = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++)
                maze[i][j] = s.charAt(j) - '0';
        }

        /* logic */
        int[] drow = {0, 0, 1, -1};
        int[] dcol = {1, -1, 0, 0}; // 동서남북

        Queue<Pos> queue = new LinkedList<>();
        queue.offer(new Pos(0, 0));
        visit[0][0] = true;

        boolean dest = false;
        int path = 0;
        while (!queue.isEmpty()) {
            Pos cur = queue.poll();
            int row = cur.row;
            int col = cur.col;

            for (int d = 0; d < 4; d++) {
                int nrow = row + drow[d];
                int ncol = col + dcol[d];
                if (nrow<0||ncol<0||nrow>=n||ncol>=m||maze[nrow][ncol]==0)
                    continue;
                if (visit[nrow][ncol])
                    continue;

                visit[nrow][ncol] = true;
                maze[nrow][ncol] = maze[row][col]+1;
                if (nrow==n-1 && ncol==m-1) {
                    dest = true;
                    break;
                }
                queue.offer(new Pos(nrow, ncol));
            }

            if (dest)
                break;
        }
        System.out.println(maze[n-1][m-1]);
    }
}