백준 - 2178번(미로 탐색)

문제 출처: https://www.acmicpc.net/problem/2178

문제

• N×M크기의 배열로 표현되는 미로가 있다.

• 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
• 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

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

public class Main {

    private static int[][] directions = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, };

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

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());    // 행
        int M = Integer.parseInt(tokenizer.nextToken());    // 열

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

        boolean[][] isVisited = new boolean[N][M];

        int cnt = 0;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {0, 0, 1});

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int y = curr[0];
            int x = curr[1];
            int length = curr[2];

            if (isVisited[y][x]) {
                continue;
            }

            isVisited[y][x] = true;

            if (y == N - 1 && x == M - 1) {
                cnt = length;
                break;
            }

            for (int i = 0; i < 4; i++) {
                int dy = y + directions[i][0];
                int dx = x + directions[i][1];

                if (dy >= 0 && dy < N && dx >= 0 && dx < M && map[dy][dx] == '1' && !isVisited[dy][dx]) {
                    queue.offer(new int[] {dy, dx, length + 1});
                }
            }
        }

        System.out.println(cnt);
    }

}

• 최단 경로를 찾는 문제라 BFS를 활용하여 풀었다.
• queue에 해당 좌표를 넣을 때 x, y 좌표와 함께 이동 수를 넣어서 거리를 알 수 있도록 하였다.