백준_2178 미로 탐색 (BFS)

최단 경로, 시간 탐색 -> bfs

왜? bfs는 한 레벨씩 내려가며 탐색, 목적지 도달 시 그 경로가 곧 최종경로. dfs는 모든 경로 방문해봐야함

 

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 BJ_2178 {

    static int[] dx = {0, 0, -1, 1}; //x인덱스 이동
    static int[] dy = {-1, 1, 0, 0}; //y인덱스 이동
    static int[][] arr;
    static boolean[][] visited;
    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());

        arr = new int[n][m];
        visited = new boolean[n][m];

        for(int i=0; i<n; i++) {
            char[] input = br.readLine().toCharArray();
            for(int j=0; j<m; j++) {
                arr[i][j] = input[j] - '0';
            }
        }

        bfs(0,0);

        System.out.println(new StringBuilder().append(arr[n-1][m-1]));
    }

    static void bfs(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        visited[i][j] = true;
        arr[i][j] = 1; //시작 노드 depth 1

        while(!queue.isEmpty()) {
            int[] nowNode = queue.poll();
            for(int k=0; k<4; k++) { //nowNode 기준 상하좌우 탐색
                int nextX = nowNode[0] + dx[k];
                int nextY = nowNode[1] + dy[k];

                if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                    if(arr[nextX][nextY]!=0 && visited[nextX][nextY] == false) {
                        queue.add(new int[]{nextX, nextY});
                        visited[nextX][nextY] = true;
                        //해당 노드의 깊이는 현재깊이 + 1
                        arr[nextX][nextY] = arr[nowNode[0]][nowNode[1]] + 1;
                    }
                }
            }
        }

    }
}

 

2178번: 미로 탐색