BOJ 2178번 미로 탐색 (bfs) 자바 풀이

BOJ 2178 미로 탐색 자바(java) 풀이

• 랭크 : 실버1
• 백준 온라인 저지(BOJ) 2178 미로 탐색 문제 자바 풀이
• 백준 2178 미로 탐색 문제
  
  
  

문제 정리

1. '1'은 이동할 수 있고 '0'은 이동할 수 없는 칸이다.
2. (1,1)에서 출발한다.
3. (n,m)으로 이동할때 지나야 하는 최소의 칸 수를 구해여라

• 시작 위치와 도착위치도 포함하여 칸을 센다.
  
  
  

문제 풀이

이 문제는 모든 경우를 따져봐야 합니다. 즉 완전 탐색입니다.
완전 탐색을 위해서 bfs를 이용해야 합니다. dfs를 이용해서 탐색하게 되면 시간초과를 만나게 됩니다.
한쪽만 잘 못 파고 들어가게 되면 dfs 같은 경우 오래 걸릴 수 있기 때문입니다.
이 문제는 최단 거리를 구하라는 뜻과 같습니다. 최단 거리를 구하는 문제의 경우에
dfs보다는 bfs를 이용해서 푸는 것이 좋습니다.

bfs

bfs의 구현에서 주의할 점은 # queue에 좌표를 넣자마자 visited 배열을 체크해주는 것이 중요합니다.
queue를 사욯하여 구현하였고 x,y좌표와 현재까지 이동한 거리를 저장할 수 있도록 Pos 클래스를 작성하였습니다.

미로 탐색 자바 코드

코드를 아래 첨부합니다. 궁금하신 점은 댓글로 남겨주세요!!

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

class Pos {
    int x;
    int y;
    int dist;

    Pos(int x, int y, int dist){
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}

class Main{    
    static int n,m;
    static int arr[][];
    static boolean[][] visited;
    static int start;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] temp = br.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        arr = new int[n][m];
        for(int i=0; i<n; i++){
            String[] temp2 = br.readLine().split("");
            for(int j=0; j<m; j++){
                arr[i][j] = Integer.parseInt(temp2[j]);
            }
        }

        visited = new boolean[n][m];
        visited[0][0] = true;
        System.out.println(bfs(0, 0));

        br.close();
    }

    public static int bfs(int x, int y) throws IOException {
        Queue<Pos> q = new LinkedList<>();

        // 위, 아래, 왼, 오
        int[] xdir = {-1, 1, 0, 0};
        int[] ydir = {0,0,-1,1};

        q.offer(new Pos(x,y, 1));
        visited[x][y] = true;
        while(!q.isEmpty()){
            Pos p = q.poll();
            int a = p.x;
            int b = p.y;
            int dist = p.dist;

            if(a == n-1 && b == m-1)
                return dist;

            for(int i=0; i<4; i++){
                int dx = a + xdir[i];
                int dy = b + ydir[i];

                if(isValidPosition(dx, dy) && !visited[dx][dy]){
                    q.offer(new Pos(dx,dy, dist+1));
                    visited[dx][dy] = true;
                }
            }
        }
        return 0;
    }

    public static boolean isValidPosition(int x, int y){
        if(x < 0 || x >= n || y < 0 || y >= m || arr[x][y] == 0)
            return false;
        return true;
    }
}