[이코테 by Java] BFS - 미로 탈출

문제
A는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력 조건

• 첫째 줄에 두 정수 N, M(4 ≤ N, M ≤ 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력 조건
첫째 줄에 최소 이동 칸의 개수를 출력한다.

예제

5 6
101010
111111
000001
111111
111111

10

💡아이디어

'최소 칸의 개수'에서 DFS보다는 BFS로 풀어야 함을 확인.
여러 경로 중 최단 경로를 구해야 하기 때문에, 시작 노드에서 여러 갈래로 뻗어가는 BFS가 사용하기에 더 적합.
(1) 미로의 첫 칸부터 시계방향으로 이동할 수 있는 다음칸의 케이스들을 확인한다. 가능한 케이스들을 방문처리 하고, Queue에 넣는다. 방문처리는 전 칸의 값에 +1 을 해준다.
(2) 1의 과정을 반복한다.
(3) 마지막 출구칸이 갖는 값을 출력한다.

🖍️문제풀이

package EscapeMaze;

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

public class Main {

    static class Node {
        private int x;
        private int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return this.x;
        }

        public int getY() {
            return this.y;
        }
    }

    public static int N; // 세로 길이
    public static int M; // 가로 길이
    public static int[][] graph; // 미로
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};
    
    public static void main (String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String firstLine = br.readLine();
        N = Integer.parseInt(firstLine.split(" ")[0]);
        M = Integer.parseInt(firstLine.split(" ")[1]);
        
        // 미로 초기화
        graph = new int[N][M];
        
        for (int i=0; i<N; i++) {
            String[] line = br.readLine().split("");

            for (int j=0; j<M; j++) {
                graph[i][j] = Integer.parseInt(line[j]);
            }
        }

        int answer = bfs(0,0);

        bw.write(String.valueOf(answer));

        br.close();
        bw.close();
    }

    public static int bfs(int x, int y) {

        Queue<Node> queue = new LinkedList<>();
        graph[x][y] = 1; // 첫 칸 방문처리
        queue.offer(new Node(x, y));

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = currentNode.getX() + dx[i];
                int ny = currentNode.getY() + dy[i];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) { // 이동 불가능 1 (미로를 벗어남)
                    continue;
                }

                if (graph[nx][ny] == 0) { // 이동 불가능 2 (괴물있음)
                    continue;
                }

                if (graph[nx][ny] == 1) { // 이동 가능하면
                    graph[nx][ny] = graph[currentNode.getX()][currentNode.getY()] + 1; // 다음 노드값 - 현재 노드 값 + 1
                    queue.offer(new Node(nx, ny)); // 방문처리
                }
            }
        }

        return graph[N-1][M-1];
    }
}