(문제 해결) B2178 미로 찾기

미로 찾기

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

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));
    }
}

문제를 해결하는 방법
문제는 최소 셀 수를 찾는 것입니다. 최단 경로 문제오전.
FSO~이다 가까운 매듭에서 검색 최단 경로보장하다
좌표로 검색할 때 대상은 남동쪽이므로 동, 남, 서, 북의 순서로 검색해야 합니다.
방문한 좌표를 다시 방문하지 않으려면 방문 규정이게 필요해
재방문한 좌표에 계속 1을 더하면 목적지는 arr(N-1)(M-1)이 된다. 최단 경로나올 것이다