[백준] 2178번 - 미로 탐색(BFS)

최단거리를 구하는 문제 ... -> BFS 사용!

 

 

BFS 처리하는 과정

1. 시작 노드 A를 방문한다.

- 시작 정점을 방문하여 방문 표시 한 후 해당 노드를 enqueue 한다.

 

2. 큐에서 첫번째 정점을 제거하고 제거된 정점과 인접한 정점에 대하여 방문하지 않은 정점을 방문한다.

- 큐에서 꺼낸 노드를 방문한다.

- 이 노드와 인접하는 노드들을 모두 방문한다.

- 인접한 노드가 없으면 큐의 맨 앞에서 노드를 꺼낸다.

 

3. 큐가 소진될 때까지 위 과정을 반복한다.

 

 

 

앞서 DFS로 풀었던 2667번과 비슷하게 풀 수 있는 유형이라 어렵지 않게 풀 수 있었던 것 같다!

 

package 백준.dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class baekjoon_2178 {

    static int[][] arr, distance;
    static boolean[][] isVisited;
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dirX = {0, 0, -1, 1};
    static int[] dirY = {-1, 1, 0, 0};
    static int N, M, nowX, nowY;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            String[] st = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st[j]);
            }
        }
        System.out.println(BFS(0, 0));
    }

    public static int BFS(int x, int y) {
        isVisited = new boolean[N][M];
        queue.add(new int[]{x, y});
        isVisited[x][y] = true;
        distance = new int[N][M];
        distance[x][y] = 1;

        while (!queue.isEmpty()) {
            int curX = queue.peek()[0];
            int curY = queue.peek()[1];
            queue.poll();
            for (int i = 0; i < 4; i++) {
                nowX = dirX[i] + curX;
                nowY = dirY[i] + curY;
                if (nowX >= 0 && nowX < N && nowY >= 0 && nowY < M) {
                    if (arr[nowX][nowY] == 1 && !isVisited[nowX][nowY]) {
                        isVisited[nowX][nowY] = true;
                        queue.add(new int[]{nowX, nowY});
                        distance[nowX][nowY] = distance[curX][curY] + 1;
                    }
                }
            }
        }
        return distance[N - 1][M - 1];
    }
}

 

이동 거리를 저장하는 distance 배열을 추가하여, BFS가 최단 거리를 리턴할 수 있도록 하였다.