<Algorithm> 35. 2178번 미로 탐색

1. 2178번 미로 탐색

• 기본 BFS 문제, 주의할점은 처음에 DFS로 접근을 했는데 시간초과가 발생했다. 1이 많을 경우 경로가 무수히 많기 때문이었다.  

• 영역이나 경우의 수를 묻는 문제가 아닌 최단경로 문제일 경우에는 BFS로 접근하는 것이 좋을 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main{
    
    static boolean[][] visited;
    static int[][] dist;
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] arr = new int[N][M];
        visited = new boolean[N][M];
        dist = new int[N][M];
        
        for(int i = 0; i < N; i ++) {
            String temp = br.readLine();
            for(int j = 0; j < M; j++) {
                arr[i][j] = temp.charAt(j) - '0';             
            }
        }
        dist[0][0] = 1;
        Queue<Coordinate> queue = new LinkedList<>();
        queue.add(new Coordinate(0, 0));
        
        bfs(arr, queue, N, M);
        
        System.out.println(dist[N-1][M-1]);
    }
    
    public static void bfs(int[][] arr, Queue<Coordinate> queue, int N, int M) {
        
        int[] dx = {0, 0, 1, -1}; 
        int[] dy = {1, -1, 0, 0};
        
        while(!queue.isEmpty()) {
            
            Coordinate loc = queue.remove();
            int x = loc.x;
            int y = loc.y;
            
            for(int i = 0; i < dx.length ; i ++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && arr[nx][ny] == 1) {
                    queue.add(new Coordinate(nx, ny));
                    dist[nx][ny] = dist[x][y] + 1;
                    visited[nx][ny] = true;
                    if(nx == N-1 && ny == M-1)return;
                }
            }
        }
    
      }
}
class Coordinate{
    int x;
    int y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}