[문제풀이] B2178 미로탐색

미로탐색

---

  🪅 시뮬레이션 유형의 문제에서 배열 dx, dy를 이용할 수 있느냐
  🪅 문제의 조건에 맞는 범위를 벗어났을 때, 예외를 처리할 수 있느냐  
  🪅 BFS를 구현할 수 있느냐 => 큐를 이용

📌 int a = arr[i].charAt(j) -'0'; // 문자에서 '0'을 빼고 int 변수에 넣어주면 해당 문자의 유니코드 값이 나온다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 백준 2178번 미로탐색
 * 
 * 입력:
 * 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 
 * 각각의 수들은 붙어서 입력으로 주어진다.
 *
 * 출력:
 * 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
 *
 */
public class Main {
    static int N;
    static int M;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] arr2d;
    static boolean[][] isVisited;
    public static void BFS(int x, int y) {
        Queue<Integer[]> queue = new ArrayDeque<>();
        isVisited[x][y] = true;
        queue.offer(new Integer[] {x,y});
        while(!queue.isEmpty()) {
            Integer[] cur = queue.remove();
            for(int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                // 범위를 벗어나면 continue
                if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if(arr2d[nx][ny] != 0 && !isVisited[nx][ny]) {
                        isVisited[nx][ny] = true;
                        arr2d[nx][ny] = arr2d[cur[0]][cur[1]] + 1;
                        queue.offer(new Integer[] {nx, ny});
                    }
                }
            }
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(token.nextToken());
        M = Integer.parseInt(token.nextToken());
        String[] arr = new String[N];
        arr2d = new int[N][M];
        isVisited = new boolean[N][M];
        // 한줄씩 입력받기
        for(int i = 0; i < N; i++) {
            arr[i] = br.readLine();
        }

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < arr[i].length(); j++) {
                arr2d[i][j] = arr[i].charAt(j)-'0';
            }
        }
        BFS(0,0);
        System.out.println(arr2d[N-1][M-1]);
    }
}

💡 문제 접근 방법
최소칸 수를 구하는 문제이니까 최단경로 문제이다.
BFS는 가까운 노드부터 탐색하니, 최단경로를 보장한다.
좌표를 탐색할 때, 목적지가 동남쪽에 있으니, 동남서북 순서로 탐색해야한다.
방문한 좌표를 또 방문하지 않기 위해 방문배열이 필요하다.
새로 방문한 좌표에 있는 값 1을 계속 더해주면, 목적지인 arr[N-1][M-1]에는 최단경로가 나오게 된다.