[Baekjoon] 2178 – 미로

문제

솔루션 프로세스

너비 우선 검색 진행(현재 깊이에서 갈 수 있는지 확인)

N,M에 도달했을 때의 깊이를 반환합니다.

일회성 이동의 경우 모든 필드(이동 횟수) + 1을 지정하여 계산

답변

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int() dx = {0, 1, 0, -1};
    static int() dy = {1, 0, -1, 0};

    static int N;
    static int M;
    static int()() arr;
    static boolean()() visited;

    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());
        arr = new int(N+1)(M+1);
        visited = new boolean(N+1)(M+1);

        for(int i = 1; i <= N; i++){
            String str = br.readLine();
            for(int j = 1; j <= M; j++){
                arr(i)(j) = str.charAt(j-1) - '0';
            }
        }
        //--- 입력 종료

        BFS(1, 1);

        System.out.println(arr(N)(M));
    }

    static void BFS(int i, int j){
        Queue<int()> queue = new LinkedList<>();
        queue.offer(new int() {i, j});
        visited(i)(j) = true;
        while(!queue.isEmpty()){
            int now() = queue.poll();
            for(int k = 0; k < 4; k++){
                int x = now(0) + dx(k);
                int y = now(1) + dy(k);
                if((x >= 1) && (y >= 1) && (x <= N) && (y <= M)){
                    if((arr(x)(y) != 0) && (!visited(x)(y))){
                        visited(x)(y) = true;
                        arr(x)(y) = arr(now(0))(now(1)) + 1;
                        queue.add(new int() {x, y});
                    }
                }
            }
        }
    }

}

​​알고리즘 분류

– 그래프 이론

– 다이어그램 탐색

– 너비 우선 검색