[백준 2178, Java] 미로 탐색

문제

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

접근

 (0,0)에서 (N-1,M-1)까지 이동할 때 최단거리를 구하는 문제이다. 탐색이므로 dfs로도 풀 수 있지만, dfs로 풀경우 모든 경우를 탐색하게 되므로 시간복잡도는 O(4^MN)가 된다. 이 경우 시간초과가 나므로 dfs로 풀면 안된다. 

 

 최단거리라고 했으므로 bfs로 풀어야한다. 

 

 

코드

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

public class Main {
    public static int N;
    public static int M;
    public static int[][] map;
    public static boolean[][] visited;
    public static final int PATH_THROUGH = 1;
    public static final int PATH_BLOCKED = 0;

    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, 1, 0, -1};

    //dfs
    public static int minCount = 10000;

    //bfs
    public static class Point{
        int x;
        int y;
        int distance;

        Point(int x, int y, int distance){
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
    }
    public static Queue<Point> queue;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] line;

        line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);

        map = new int[N][M];
        visited = new boolean[N][M];

        for(int r = 0; r<N; r++){
            line = br.readLine().split("");
            for(int c = 0; c<M; c++){
                map[r][c] = Integer.parseInt(line[c]);
            }
        }

        queue = new LinkedList<>();
        int minDistance =getPathByBfs();

        bw.write(String.valueOf(minDistance));
        bw.flush();

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

    }
    // (x,y)에서 (N-1, M-1)까지 경로구하기 (count : (0,0)에서 (x,y)까지 지나온 길)
    // (x,y)에서 (N-1, M-1)까지 경로가 있다 = (x,y)가 지나갈 수 있는 길이다 && (x,y)의 이웃한  칸에서 (N-1, M-1)까지 경로가 있다
    // 지나갈 수 있는 길 = 범위 안의 칸 + 지나간 적 없는 칸 + 지나갈 수 있는 칸
    public static void getPathByDfs(int x, int y, int count){
        if(x==N-1 && y==M-1){
            minCount = Math.min(minCount, count);
        }
        else if(x<0 || y<0 || x>=N || y>=M){
            return;
        }
        else if(visited[x][y]){
            return;
        }
        else if(map[x][y] ==PATH_BLOCKED){
            return;
        }
        else {
            visited[x][y] = true;
            for(int d= 0 ;d<4 ;d++){
                int nx = x + dx[d];
                int ny = y + dy[d];

                getPathByDfs(nx, ny, count+1);
            }
            visited[x][y] = false;
        }
    }

    // (0,0)에서 (N-1, M-1)까지 이동하는 최소 횟수
    public static int getPathByBfs(){
        //초기화
        queue.add(new Point(0,0,1));
        visited[0][0] = true;
        int minDistance = 1;
        //순회
        while(!queue.isEmpty()){
            Point currentPoint = queue.poll();

            if(currentPoint.x ==N-1 && currentPoint.y ==M-1){
                minDistance = currentPoint.distance;
                break;
            }
            else{
                for(int d = 0 ;d<4; d++){
                    int nx = currentPoint.x + dx[d];
                    int ny = currentPoint.y + dy[d];

                    if(nx>=0 && ny>=0 && nx<N && ny<M){
                        if(!visited[nx][ny] && map[nx][ny] ==PATH_THROUGH){
                            Point nextPoint = new Point(nx, ny, currentPoint.distance+1);
                            visited[nx][ny] = true;
                            queue.add(nextPoint);
                        }
                    }
                }
            }
        }
        return minDistance;
    }
}