[BaekJoon] 백준 - 미로 탐색

 

N x M 으로 구성된 미로에서 1, 1 부터 시작해서 N, M 까지 갈 수 있는 최단거리를 구하는 문제

 

1, 1부터 BFS 탐색을 통해 연결된 미로를 탐색해나가면 된다. 

 

이미 탐색이 완료된 칸이 있을 수 있으므로 visited 를 사용하여 Queue 에 삽입한다. 

 

 

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


public class Main {
    static int N;
    static int M;
    static int[][] MIRO;
    static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] tmp = br.readLine().split(" ");
       
        N = Integer.parseInt(tmp[0]);
        M = Integer.parseInt(tmp[1]);
        
        MIRO = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];
        
        for(int i = 1; i<N+1; i++) {
            String[] input = br.readLine().split("");
            
            for(int j = 1; j<M+1; j++) {
                MIRO[i][j] = Integer.parseInt(input[j-1]);
                visited[i][j] = false;
            }
        }
    
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 1, 1});
        int[] x = {1, -1, 0, 0};
        int[] y = {0, 0, 1, -1};
        
        
        while(!queue.isEmpty()) {
            int[] q = queue.poll();
            if (q[0] == N && q[1] == M) {
                System.out.println(q[2]);
                break;
            }
            
            visited[q[0]][q[1]] = true;
            
            for(int i = 0; i<4; i++) {
                int ny = q[0] + y[i];
                int nx = q[1] + x[i];
                
                if (ny > 0 && ny < N + 1 && nx > 0 && nx < M + 1) {
                    if (MIRO[ny][nx] == 1 && !visited[ny][nx]) {
                        visited[ny][nx] = true;
                        queue.add(new int[]{ny, nx, q[2] + 1});
                    }
                }
            }
        }
        
        
    }
    
}