백준/2178번/Java - 미로 탐색 (BFS)

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

2178번: 미로 탐색

---

깊이를 우선적으로 탐색하는 DFS와 달리 BFS는 넓이를 우선적으로 탐색한다.

DFS가 어떤 노드에서 갈 수 있는 다음 노드, 그리고 다음 노드에서 갈 수 있는 다다음 노드를 찾아 깊숙하게 탐색을 이어간다면,

BFS는 어떤 노드에서 갈 수 있는 여러 노드들을 모두 방문하고 나서야 다음 깊이의 노드들을 탐색한다.

이를 위해 BFS는 queue를 사용하여 구현하며

특정 목표 노드까지의 최단 거리를 구하기에 용이하다.

 

2178번 역시 항상 도착위치로 이동할 수 있는 경우를 구하는 문제이므로, 도착 위치까지의 거리를 구하기 위해 BFS를 활용했다.

 

맨 처음 시작 노드를 큐에 삽입한다.

현재 시작 위치에 방문하였으므로 시작 위치를 방문처리하고 큐에서 꺼낸다.

상하좌우 이동이 가능한 문제이므로 반복문을 통해 상하좌우를 돌며 방문이 가능한 다음 위치들을 찾아 모두 방문한다.(+방문처리)

방문한 노드들은 큐에 삽입한다.

 

큐에서 노드를 꺼내 위의 과정을 큐가 비어있을 때 까지 반복한다.

 

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

public class Main {
    static int N, M;
    static boolean[][] visited;
    static int[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    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());

        // N행 M열
        map = new int[N][M];
        visited = new boolean[N][M];
        //배열 초기화.
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(s.substring(j, j+1));
            }
        }

        bfs(0,0);
        //문제에서는 0,0이 아닌 1,1부터 시작하므로...
        System.out.println(map[N-1][M-1]);

    }

    private static void bfs(int x, int y) {
        //시작 위치를 큐에 삽입
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x, y});
        //시작 위치 방문 처리
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            //현재 위치를 큐에서 꺼냄
            int[] now = queue.poll();
            //상하좌우 탐색
            for(int i=0; i<4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if(map[nx][ny] > 0 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    //시작점의 값은 1이고 depth는 1이다.
                    //map 배열의 값을 통해 depth를 표현할 수 있다. whiile문이 한번 돌 때마다 깊이가 + 1 되는 것이므로
                    //다음 깊이의 노드들은 이전 깊이보다 + 1 한 값을 갖게 된다.
                    //결과적으로 map 배열에 각 위치의 깊이가 나타난다.
                    map[nx][ny] = map[now[0]][now[1]] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}