[백준 - 2178/ 자바(Java)] 미로 탐색 문제 BFS로 해결하기

BFS에 대한 개념을 먼저 공부해야 한다면 아래 포스팅을 먼저 보고 문제를 푸시는 걸 권장합니다.

https://sunro1994.tistory.com/181

[백준 -24480 ] java , 알고리즘 수업 - 깊이 우선 탐색 2

이번 문제입니다!

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

이번 문제는 DFS와BFS모두 가능하지만 효율을 위해 BFS를 선택했습니다.
최악의 경우에는 DFS와 효율이 같겠지만 BFS는 모든 경로를 동시에 검색하기 때문에 DFS보다 빠른 탐색이 가능합니다.
이번 코드의 핵심!은 배열을 이용한 상하좌우 탐색 및 검색입니다.

Do it! 알고리즘 자바편

정점을 시작으로 검색을 할 때 상하좌우 탐색을 해야 합니다. 또한 예외를 방지하기 위한 조건들이 필요합니다.

조건1. 탐색 시 배열의 범위를 벗어나면 안된다.

조건2. 탐색 시 0일경우에는 해당 노드로 이동하면 안된다.

조건3. 방문한 노드는 다시 방문해서는 안된다.

조건4. 탐색하는 인덱스는 배열의 범위보다 작아야한다.

 

이러한 조건을 모두 만족한 인덱스는 +1을 해줍니다. 

이와 같이 계속해서 조건에 맞는 노드들의 수를 증가하다보면 마지막 노드에 접근할 수 있는 최소값이 출력이 되죠!

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

public class BFS {
    //상하좌우 이동을 위한 방향 배열
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    static boolean[][] visited;
    static int[][] A;
    static int N,M;
    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());
        A = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j = 0; j < M; j++) {
                A[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }
        BFS(0, 0);
        System.out.println(A[N-1][M-1]);

    }

    private  static  void  BFS( int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i,j});
        while (!queue.isEmpty()) {
            int now[] = queue.poll();
            visited[i][j] = true;
            for (int k = 0; k < 4; k++) { //상하좌우탐색을 위해 4번 돌림
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if (x >= 0 && y >= 0 && x < N && y < M) { //배열을 넘어가면 안되고
                    if (A[x][y] != 0 && !visited[x][y]) { //방문한곳이면 안되고 0이여서 넘어가면 안됨
                        //이제 갈 수 있는 곳
                        visited[x][y] = true;
                        A[x][y] = A[now[0]][now[1]] + 1;
                        queue.add(new int[] {x, y});
                    }
                }
            }
        }
    }
}