[백준] 2178 미로 탐색 (BFS)

 

설명

N x M 배열이 있을 때에 1이 이동 가능한 위치이고, 0이 이동 불가한 위치이다. 

N,M 위치까지 가는 방법에 대해서 최소한의 경우를 출력해준다.

 

소스 해석

• map에다가 문제에서 주어진 값 0, 1을 저장
• 특정 부분을 방문했는지 체크하기 위해 visited 배열 운영
• queue를 활용해서 시작 위치를 넣어주면서 BFS 시작
• for문을 활용해서 이동가능한 상화좌우를 탐색하고, 
  이동 가능한 부분이 있으면 새로운 queue를 생성해서 계속해서 탐색할 수 있도록 함.
• 이동이 불가하면 queue에 값을 넣지 않음
• 모든 queue에 있는 값이 이동이 불가하면 queue에 추가적으로 값을 넣지 않기 때문에 queue가 비어져서 while(탐색)이 종료됨.

 

package Baekjoon;

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

public class BOK_2178 {
    static int[][] map;
    static int N;
    static int M;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for(int i=0; i<N; i++){
            String s = br.readLine();
            for(int j=0; j<M; j++){
                map[i][j] = s.charAt(j) - '0';
            }
        }
        visited = new boolean[N][M];
        visited[0][0] = true;
        bfs(0, 0);
        System.out.println(map[N-1][M-1]);
    }
    public static void bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x,y});

        while(!q.isEmpty()){
            int now[] = q.poll();
            int nowX = now[0];
            int nowY = now[1];

            for(int i=0; i<4; i++){
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) // 범위 벗어나면
                    continue;
                if(visited[nextX][nextY] || map[nextX][nextY] == 0) // 이미 방문했거나 막혀있으면
                    continue;
                q.add(new int[] {nextX, nextY});
                map[nextX][nextY] = map[nowX][nowY] + 1;
                visited[nextX][nextY] = true;
            }
        }
    }
}