[Baekjoon] 2178 - 미로 탐색

📝 문제

 

 

 

 

🔑 풀이 과정

지나가야 하는 칸 수의 최솟값을 찾는 것이 이 문제의 목표.

완전 탐색을 진행하면서 몇 번째 깊이에서 원하는 값을 찾을 수 있는지를 구하는 것과 동일

 

BFS를 사용해서 (N,M)에 도달 했을 때의 깊이를 출력한다.

 

① 상하좌우 4방향으로 이동하면서, 이동할 수 있고 아직 방문하지 않은 경우 방문을 진행한다.

② 방문할 때, 방문한 칸에 이동 전 노드의 값 + 1을 계산한 값을 넣는다. (이동횟수를 추가하는 것임)

 

예제2를 그림으로 표현한 것.

좌측이 주어진 미로.

우측이 이동 횟수.

 

 

🔓 답안

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

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색