[백준] 2178번 - 미로 탐색 [Java]

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

 

[백준] 2178번 - 미로 탐색 [Java]

[백준] 2178번 - 미로 탐색 [Java]

---

1.  아이디어

 

미로의 최단 거리는 BFS로 구할 수 있다.

---

2. 문제풀이

 

미로는 0과 1로 이루어져 있는데 코드를 간단하게 짜기 위해 char 타입의 2차원 배열로 처리했다.

최단 거리는 Queue가 빌 때까지 반복하는데 내부에서 Queue의 크기만큼 반복 후 길이를 1 더하는 방법으로 최단 거리를 계산할 수 있다.

미로가 항상 도착 위치로 이동할 수 있어서 문제는 없지만 Queue가 다 비었을 때도 도착하기 못하면 -1을 출력하도록 작성했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        char[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        System.out.println(bfs(N, M, map));
    }

    private static int bfs(int N, int M, char[][] map) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});

        boolean[][] visited = new boolean[N][M];
        visited[0][0] = true;

        int dist = 1;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                int[] item = q.poll();

                if (item[0] == N - 1 && item[1] == M - 1) return dist;

                for (int dir = 0; dir < 4; dir++) {
                    int nr = item[0] + dr[dir];
                    int nc = item[1] + dc[dir];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
                    if (map[nr][nc] == '0' || visited[nr][nc]) continue;

                    q.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                }
            }

            dist++;
        }

        return -1;
    }

}

---

4. 후기