[BFS] 백준 #2178 / 미로 탐색

SW Expert Academy의 '탈주범 검거' 문제와 풀이 방식이 동일하다.

BFS의 Level 단계를 파악하는 것이 핵심 포인트! 그래서 파라미터로 time을 넘겨줘야 한다.

우선 문제 파악부터 해보쟈

[문제 요약]

1. N x M 크기의 배열의 미로가 있다.

2. 1은 이동 가능, 0은 이동 불가능을 의미한다.

3. (1,1)에서 출발하여 (N,M)의 위치로 이동할 때, 지나야 하는 최소의 칸 수는~?

4. 칸을 셀 때는, 시작 위치 (1,1)과 도착 위치 (N,M)을 포함해야 한다.

[Input]

1. 행 N, 열 M 입력

2. N x M의 미로가 주어진다. 각 수는 붙어서 입력으로 주어진다.

   ㄴ Re : 붙어서 입력 받아지는 숫자들을 분리해서 맵에 넣어주어야 한다.

3. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

   ㄴ Re : 도착 지점으로 무조건 갈 수 있으니 다른 경우는 신경쓰지 말란 소리!

Output은 평범해서 생략. 그냥 최소 시간을 출력하면 된다.

[Key Point]

1. 각 행을 String으로 입력 받고, charAt을 이용하여 아스키 값을 받은 뒤, int형으로 변환!

   여기서 주의할 점은, 0은 아스키코드 값으로 '48'이다.

2. DFS가 아닌 BFS로 탐색해야 한다. 이 문제는 BFS로 얼마 만큼의 깊이 까지 들어가야 도착점에 도달하는지를 묻는 문제이다.

[Code]

 
/*
 * 백준 2178번, 미로 탐색 문제.
 * 
 * 1. N*M크기의 배열로 표현되는 미로가 있다.
 * 2. 미로에서 1은 이동 가능, 0은 이동 불가능을 나타낸다.
 * 3. 이 때, (1,1)에서 출발하여 (N,M)으로 이동할 때, 지나야 하는 최소 칸의 수를 구하여라.
 * 
 * 
 */
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.awt.Point;
 
public class boj_2178_miro {
 
    private static int Map[][];
    private static boolean visited[][];
    private static int N, M;
    private static int total;
    private static int xx[] = { -1, 1, 0, 0 };
    private static int yy[] = { 0, 0, -1, 1 };
 
    public static void bfs(int x, int y,int time) {
        visited[x][y] = true;
        Queue<Point> Q = new LinkedList<Point>();
        Queue<Integer> level = new LinkedList<>();
        Q.add(new Point(x, y));
        time++;
        level.add(time);
 
            while (!Q.isEmpty()) {
                int cx = Q.peek().x; // current x
                int cy = Q.peek().y; // current y
                int Time = (int)level.poll();
                Q.poll();
    
                if (cx == N - 1 && cy == M - 1) { 
                    total = Time++; 
                    return; 
                }
                
                for (int i = 0; i < 4; i++) {
                    int nx = cx + xx[i]; // next x
                    int ny = cy + yy[i]; // next y
                    if (nx < 0 || ny < 0 || nx > N - 1 || ny > M - 1)
                        continue;
                    if (visited[nx][ny])
                        continue;
                    if (Map[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        Q.add(new Point(nx, ny));
                        level.add(Time+1);
                    }
                }
            }
 
    }
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt();
        M = sc.nextInt();
        Map = new int[N][M];
        visited = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
            String temp = sc.next();
            for (int j = 0; j < M; j++) {
                Map[i][j] = (int) temp.charAt(j) - 48;
            }
        }
        bfs(0, 0, 0); // 0,0에서 bfs 시작.
        System.out.println(total);
    }
}